3
$\begingroup$

A group of people is sitting around a round table. They have a coffee break. When they get back, they sit down randomly.

Interestingly, they all notice that the 8 closest people sitting next to each of them (the 4 on their left and the 4 on their right) are completely different to before.

At least how many people are sitting around the table?

|improve this question
$\endgroup$
5
$\begingroup$

I have found a possible arrangement, which gives an upper bound of

$26$ people.

Here is the arrangement:

Name the people A to Z around the table at the first sitting. 

 ABCDEFGHIJKLMNOPQRSTUVWXYZ  - first sitting
 AVQLGBWRMHCXSNIDYTOJEZUPKF  - second sitting
If you number the seats from $0$ to $25$, then the person who first sat at seat $x$ will later sit at $5x \mod 26$. This spaces adjacent people far enough apart that they are no longer share the same group. At the other extreme, people who were 4 apart end up being $26-5*4=6$ apart in the opposite direction around the table so are also in different groups.

With the help of hexomino and ffao this is proved to be the best possible.

First @hexomino pointed out there is a very close lower bound of

$25$ people.

The reason is:

a group of five people in a row at the first sitting must all be separated from each other in the second sitting, so there must be at least 4 people between any two of them. This means that there are at least $25$ people at the table.

Then @ffao's comment showed why the above lower bound is not attainable, proving that arrangement above has the fewest possible number of people.

Continuing the argument above, if ABCDE were in a row in the first sitting, in the second sitting they can be in any order but must have at least four people separating any two of them. Now consider person F, who was adjacent to E in the first sitting. This person cannot be placed anywhere at the table, because they must be at least 4 away from each of BCDE, and the only seat that qualifies is already occupied by A.

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Nice. It seems to me that you could show that the lower bound is just one less than this just by considering five consecutive people in the original arrangement and noting that they all have to be separated from each other in the result. $\endgroup$ – hexomino Sep 7 '18 at 9:05
  • $\begingroup$ @hexomino Good point. I'll add that, thanks. $\endgroup$ – Jaap Scherphuis Sep 7 '18 at 9:06
  • 3
    $\begingroup$ If you have one less person and take groups ABCDE and BCDEF, wouldn't A and F have to be on the exact same spot on the second sitting? $\endgroup$ – ffao Sep 7 '18 at 9:25
  • $\begingroup$ Thanks @ffao. I have edited that into my answer. $\endgroup$ – Jaap Scherphuis Sep 7 '18 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.