People at the party and counting friends

[Archinald]

Hi
1. Homework Statement
On the party came n people. In the beginning 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

 

[haruspex]

for which the following statement is true.

What following statement?

 

[Stephen Tashi]

On the party came n people. In the beginning 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.

 

[Archinald]

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.

 

[Stephen Tashi]

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"
?

 

[haruspex]

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?

 

[Stephen Tashi]

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 ?

 

[haruspex]

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.

 

[Joffan]

I can make it work for n=6. Just don't start with K_3,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...

 

[haruspex]

I can make it work for n=6. Just don't start with K_3,3.

Quite so - there are only two regular degree 3 graphs on 6 vertices. K_3,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.

 

[Joffan]

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 :-) )