9 strangers play an ice-breaking game at a party for several rounds. For each round, they will sit around a round table and introduce themselves to their neighbors. The rule is that no one is seated next to his/her acquaintance in a new round. Suppose the game has been played for 3 rounds. Is it always possible to find a seating plan for the 4th round?
I'm tempted to say that it's possible based on pigeonhole principle:
For a given person, there are at most 3 rounds that have already taken place (rounds 1,2, and 3). In these rounds, the person has had a total of 2 × 3 = 6 neighbors (two
neighbors in each round, 3 rounds). In the 4th round, there are 9 – 6 = 3 people left that this person has not been acquainted with. Since there are 3 people left that each person hasn't been acquainted with, and each person needs 2 new neighbors, it is always possible to find a seating plan for the 4th round. This is because there are enough unacquainted people to fill the neighbor slots for each person.
However, I think it needs to relate using concepts of graph theory as well. Any help is appreciated.
Best Answer
Note that there are really two questions here:
Is it possible that people move around in a way that makes sure that after 4 rounds everybody has set next to everybody?
Is it possible that people move around in a way that makes sure that in the first 3 rounds everybody has sat next to six different people, but it is now impossible to have a 4th round in which everybody meets the last two people they haven't met?
A priori it is possible that the answer to both questions is yes (it can be done but it requires planning) or to the first question the answer is yes but to the second it is no (the problem is easy, just let people figure it out) or that the answer to the first question is no and so the second question is only of academic interest, but could still go both ways.
That said:
Here is an example that shows that the answer to the second question is yes. So people might mess up the first three rounds in a way that is irreparable. I do not know yet if there is a a positive answer to the first question or not
Suppose the seats are numbers $0, 1, \ldots, 9$. After every round, every person moves to the seat that has twice the number of their current seat (counted modulo 9).
Lets call the people $P_0 ,\ldots P_8$ based on the location of their seat in the first round.
Then in the first round person $P_a$ sits next to $P_{a-1}$ and $P_{a+1}$. In the second round this person sits in chair $2a$, so next to people in chairs $2a-1$ and $2a + 1$. These are people $(2a -1)/2$ and $(2a+1)/2$. Since $10 = 1$ (modulo 9) dividing by 2 equals multiplying by 5 and so we see the new neighbors are $P_{a - 5}$ and $P_{a + 5}$.
This means that my neighbors in the second round are the two people who were farthest away from me in the first round. Consequently the people sitting next to me in the third round are the people farthest away in the second round. For person $P_a$ these are the people sitting in chairs $2a + 4$ and $2a - 4$, during the second round so these are persons $P_{a + 2}$ and $P_{a - 2}$.
So far so good. Person $P_a$ has met everybody except $P_{a-3}$ and $P_{a+3}$ and wants to sit in between them in the last round. This is true for every value of $a$ so $P_0$ wants to sit between $P_3$ and $P_6$. But $P_3$ want to sit between $P_0$ and $P_6$ and $P_6$ wants to sit between $P_3$ and $P_0$.
Clearly this is impossible.