Rearrangement of dinner guests A dinner host wants his guests to move, between main course and dessert, so that everyone gets a complete set of new neighbours.
Guests are seated either side of a long table.  Most guests have five neighbours - left, right, opposite, and opposite's left and right.  The four guests, at either end of both sides of the table, have only three neighbours.
Why is it impossible to arrange this with seven people on either side of the table, but there are exactly $2^{17} = 131072$ solutions with eight people on either side?
 A: Partial answer: There is no solution for seven people per side.
Let a seating for the main course be given. Suppose there is an allowed seating for dessert. Some person, call him $0$, has to move to a center position for dessert. Person $0$ has a person $1$ opposite him, and he also sits next to two people $2$ and $3$ opposite each other, for dinner. The seating for dessert looks as follows, where the stars are forbidden seats for $1,2,3$, and dashes are allowed seats.
--*0*--
--***--

Thus $1,2,3$ have to sit among the four seats to the left or the four seats to the right. At least two of $1,2,3$ will have to sit on the same side (left or right), and will be neighbors again. Contradiction.
A: (This is too long for a comment and not part of the answer I gave a year ago, so I'm posting it as a new answer under community wiki.)
I made an exhaustive computer search of the solutions for eight people per side and found out that there is really only one unique solution up to symmetries. Stating this fact and showing the structure of the solution might help someone to come up with a full proof (see the edit for a sketch of a proof). Now, let us label the guests at the dinner table as
 0  1  2  3  4  5  6  7
 8  9 10 11 12 13 14 15

The unique dessert table arrangement up to symmetries is:
 1  5  9 13  0  4  8 12
 3  7 11 15  2  6 10 14

All other dessert table arrangements are obtained by swapping guests opposite to each-other, flipping the table left-to-right, or swapping two people who were opposite to each-other during dinner (0 and 8, for instance). In total this gives $2^8\times 2\times 2^8=2^{17}$ solutions.
EDIT: All other arrangements can be ruled out in an easy but tedious manner. I won't write out the entire argument, but one can proceed as follows. One can prove each of the following statements by assuming the opposite and deriving a contradiction by checking a very small number of cases by a manual depth-first-search.


*

*The four center chairs of the dessert table must contain precisely two guests who were previously in a corner. WLOG these are guests 0 and 15 and they must sit diagonally opposite each other, with 0 to the right and 15 to the left.

*All even-numbered guests must be on the right side, and all odd-numbered guests must be on the left side.

*The dessert guest opposite 0 must be 2 or 10, and likewise the dessert guest opposite 15 must be 13 or 5. Then the positions of all other guests fall into place.
