1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

People at the party and counting friends

  1. Dec 13, 2014 #1
    Hi
    1. The problem statement, all variables and given/known data

    On the party came n people. In the begining all of them have had exactly 3 friends among party members. During party some people made new friends and at the end of the party everyone had exactly 4 friends among party members. Set all numbers n for which the following statement is true. (if person A knows person B, then person B knows person A)
    2. Relevant equations


    3. The attempt at a solution
    I found only some law that says -> "In any party of six people either at least three of them are (pairwise) mutual strangers or at least three of them are (pairwise) mutual acquaintances.", but I don't have an idea how to use that to solve this. Making combinations of possible cases i feel like it has to be n > 6 but i have no clue how to prove that.

    Thanks in advance for all tips,
    mfg
     
  2. jcsd
  3. Dec 13, 2014 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    What following statement?
     
  4. Dec 13, 2014 #3

    Stephen Tashi

    User Avatar
    Science Advisor

    Pehaps the question is being translated from a different language or culture. Can we phrase it like this ?:

    Assume n people attend a party. Initially, each person at the party recognizes exactly 3 other attendees. At the end of the party, each person recognizes exactly 4 attendees. List the possible values of n for which the following statement can be true at the end of the party: Each person who recognizes another attendee is recognized by that attendee.

    I'm using 'recognize" as non-symmetric relation. For example, you might recognize a famous actor at a party, but the actor might not recognize you.
     
  5. Dec 13, 2014 #4
    Yes, that's right translation, but there are only symmetrical relations in question - if first person knows or recognizes second person then second person recognizes first person as well.

    EDIT - I just read again your post and realized you wrote about symmetric rule in last sentence. It's pretty late in my time zone ; ) anyway thanks for replying.
     
  6. Dec 13, 2014 #5

    Stephen Tashi

    User Avatar
    Science Advisor

    Then should the last sentence of the problem say:
    "List the possible values of n for which the following statement can be true at the end of the party: Each person recognizes every other person"
    ?
     
  7. Dec 13, 2014 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    The way I read the question,
    specified that the 'friends' relation was symmetric throughout. Archinald's subsequent posts appear to confirm that. That leaves unanswered my question as to what the 'following statement' is.
    Archinald, is it asking for what n the preceding statements are possible?
     
  8. Dec 14, 2014 #7

    Stephen Tashi

    User Avatar
    Science Advisor

    An undirected graph has n vertices. Each vertex has edges that connect it to exactly 3 other vertices. Edges are added to the graph so that each vertex has edges that connect it to exactly 4 other vertices. When this is done, all the vertices of the graph are connected to each other by edges. What are the possible values for n ?
     
  9. Dec 14, 2014 #8

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Stephen, I'm with you until this part:
    I don't see where you get that from in the OP posts.
    You can delete that sentence from your post and still have a worthwhile puzzle.
     
  10. Dec 17, 2014 #9
    I can make it work for n=6. Just don't start with K3,3. Show us the before and after graphs :-)

    If we add one friendship, that increases the friend count for 2 people from 3 to 4...
     
  11. Dec 17, 2014 #10

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Quite so - there are only two regular degree 3 graphs on 6 vertices. K3,3 cannot be extended to regular degree 4 but the other can.
    Are you asking Archinald to find the 6 vertex graph where it can be done?
    Seems to me we are still in the dark as to what the question means. Archinald has not answered my post #6, and Stephen and I have different interpretations.
     
  12. Dec 17, 2014 #11
    True - I support your interpretation, because it seems the most likely and interesting meaning. (and yes, I'd like Archinald to find that graph). My paraphrase of the problem:
    (Further, previously unstated assumption: no friendships were broken in the course of the party :-) )
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: People at the party and counting friends
  1. Counting question (Replies: 8)

  2. Counting combinations (Replies: 7)

  3. Counting permutations (Replies: 6)

Loading...