0

A question came up recently:

There is a team sitting at a round table. They all leave the table for a lunch break, and after returning to the table, each person finds that both their neighbours on the right and on the left do not sit next to them anymore. How many people may be sitting around the table? Describe all the possibilities.

Personally, I have no idea how to prove this mathematically -- all I know, after trial and error, that 1, 2, 3, and 4 don't work and 5 does. Is there a way I can prove this, and show (if they are) that greater numbers are possible?

Leo
  • 89
  • The question boils down to this: is there a Hamiltonian cycle through the complement of the cycle graph of $n$ vertices? – Dan Uznanski Jan 26 '21 at 10:47

1 Answers1

3

The question boils down to this: is there a Hamiltonian cycle through the complement of the cycle graph of n vertices?

For $n < 5$ the answer is obviously no: the complements here are the empty graph for $n = 2$ and $3$, and two separate $K_2$ graphs for $n = 4$.

For $5$, the answer is yes, and there is essentially only one way to do it: if our people are $ABCDE$ around the table originally, $ACEBD$ is the only layout that works.

For $6$ and higher, we can determine the yes-no answer as simply this: is it always true that the $n$th person can push a chair in in a place that isn't next to one of their former neighbors? And the answer to this is obviously yes: the two neighbors only block off the four spots immediately next to them, and at more than $4$ seats already placed, there are more than $4$ spots to push in a new chair!

Dan Uznanski
  • 11,025