Big Table in a Conference

Question

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?

Answer 1

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.