• Support PF! Buy your school textbooks, materials and every day products Here!

People at the party and counting friends

  • #1
2
0
Hi
1. Homework Statement

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)

Homework Equations




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
 

Answers and Replies

  • #2
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
32,711
5,029
for which the following statement is true.
What following statement?
 
  • #3
Stephen Tashi
Science Advisor
7,012
1,235
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)
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.
 
  • #4
2
0
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.
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.
 
  • #5
Stephen Tashi
Science Advisor
7,012
1,235
there are only symmetrical relations in question - if first person knows or recognizes second person then second person recognizes first person as well.
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"
?
 
  • #6
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
32,711
5,029
The way I read the question,
(if person A knows person B, then person B knows person A)
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?
 
  • #7
Stephen Tashi
Science Advisor
7,012
1,235
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 ?
 
  • #8
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
32,711
5,029
Stephen, I'm with you until this part:
When this is done, all the vertices of the graph are connected to each other by edges.
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.
 
  • #9
473
13
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...
 
  • #10
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
32,711
5,029
I can make it work for n=6. Just don't start with K3,3.
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.
Show us the before and after graphs
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.
 
  • #11
473
13
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.
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:
##n## people attended a party. In the beginning, all of them had exactly 3 friends among party members. During the party, some people made new friends and at the end of the party everyone had exactly 4 friends among party members. Find all numbers ##n## for which these events are feasible. (Friendship is symmetric: if person A is a friend of person B, then person B is a friend of person A)
(Further, previously unstated assumption: no friendships were broken in the course of the party :-) )
 

Related Threads on People at the party and counting friends

Replies
6
Views
2K
Replies
2
Views
736
Replies
5
Views
2K
Replies
3
Views
899
Replies
2
Views
1K
Replies
3
Views
779
Replies
8
Views
1K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
6
Views
1K
Replies
1
Views
1K
Top