Reorganización de los invitados a la cena

Question

El anfitrión de una cena quiere que sus invitados se muevan, entre el plato principal y el postre, para que todo el mundo tenga un conjunto completo de nuevos vecinos.

Los invitados se sientan a ambos lados de una larga mesa. La mayoría de los invitados tienen cinco vecinos: a la izquierda, a la derecha, al frente y a la izquierda y a la derecha del frente. Los cuatro invitados, situados en los extremos de ambos lados de la mesa, sólo tienen tres vecinos.

¿Por qué es imposible organizar esto con siete personas a cada lado de la mesa, pero hay exactamente $2^{17} = 131072$ soluciones con ocho personas a cada lado?

Answer 1

Respuesta parcial: No hay solución para siete personas por lado.

Que se dé un asiento para el plato principal. Supongamos que hay un asiento permitido para el postre. Una persona, llámese $0$ , tiene que pasar a una posición central para el postre. Persona $0$ tiene una persona $1$ frente a él, y también se sienta junto a dos personas $2$ y $3$ frente a la otra, para la cena. Los asientos para el postre tienen el siguiente aspecto, donde las estrellas son asientos prohibidos para $1,2,3$ y los guiones son asientos permitidos.

--*0*--
--***--

Así, $1,2,3$ tienen que sentarse entre los cuatro asientos de la izquierda o los cuatro de la derecha. Al menos dos de $1,2,3$ tendrán que sentarse en el mismo lado (izquierda o derecha), y volverán a ser vecinos. Contradicción.

Answer 2

(Esto es demasiado largo para un comentario y no forma parte de la respuesta que di hace un año, así que lo publico como una nueva respuesta en la wiki de la comunidad).

Hice una búsqueda informática exhaustiva de las soluciones para ocho personas por lado y descubrí que en realidad sólo hay una solución única hasta las simetrías. Afirmar este hecho y mostrar la estructura de la solución podría ayudar a alguien a presentar una prueba completa (ver la edición para un esbozo de prueba). Ahora, etiquetemos a los invitados a la mesa como

 0  1  2  3  4  5  6  7
 8  9 10 11 12 13 14 15

La disposición de la mesa de postres única hasta las simetrías es:

 1  5  9 13  0  4  8 12
 3  7 11 15  2  6 10 14

Todas las demás disposiciones de la mesa de postres se obtienen intercambiando a los invitados opuestos entre sí, volteando la mesa de izquierda a derecha o intercambiando a dos personas que estaban opuestas entre sí durante la cena (0 y 8, por ejemplo). En total, esto da $2^8\times 2\times 2^8=2^{17}$ soluciones.

EDITAR : Todos los demás arreglos se pueden descartar de una manera fácil pero tediosa. No escribiré todo el argumento, pero se puede proceder como sigue. Uno puede probar cada una de las siguientes afirmaciones asumiendo lo contrario y derivando una contradicción comprobando un número muy pequeño de casos mediante una búsqueda manual en profundidad.

• Las cuatro sillas centrales de la mesa de postres deben contener precisamente a dos invitados que antes estaban en una esquina. WLOG estos son los invitados 0 y 15 y deben sentarse en diagonal uno frente al otro, con el 0 a la derecha y el 15 a la izquierda.

• Todos los invitados con número par deben estar en el lado derecho, y todos los invitados con número impar deben estar en el lado izquierdo.

• El invitado de postre frente al 0 debe ser el 2 o el 10, y del mismo modo el invitado de postre frente al 15 debe ser el 13 o el 5. A continuación, las posiciones de todos los demás invitados caen en su lugar.