Problema de Oberwolfach - 30 personas en la cena en 3 mesas de 10 asientos cada uno

Question

Hay $30$ personas en un ex-alumnos de la cena, sentados en $3$ mesas redondas de $10$ escaños cada uno.

Después de cada intervalo de tiempo $\Delta t$, un cambio de posición, el evento se requiere donde todo el mundo cambia de posición de forma simultánea, con el fin de tener la oportunidad de sentarse junto a alguien diferente a su izquierda y derecha. Esto se traduce en una diferente configuración de asientos.

¿Cuál es el mínimo número de configuraciones de asientos (es decir, el número de la posición de los eventos de cambio de $+1$) necesaria para que todo el mundo se han sentado junto a cualquier otra persona sólo una vez?
NOTA - Si esto no es posible, la última condición puede ser modificado a partir de "una vez" a "al menos una vez", pero por favor, especifique en consecuencia.

Traté de trabajar por un menor número de $n$ a a $10$ de las personas, sentado, sólo en $1$ tabla, y se encontró que el número mínimo de configuraciones es $\displaystyle\bigg\lfloor\frac n2\bigg\rfloor$.

Sin embargo, esto se vuelve complicado cuando hay diferentes tablas.

Este es un ejemplo de la Oberwolfach problema, y diversos documentos y artículos sobre este están disponibles en la web, la mayoría de ellos tratan generalizada de los casos y requiere una buena comprensión de la teoría de grafos.

Se agradecería si alguien pudiera derivar una solución fácil de usar para la pregunta en este caso en particular.

Answer 1

Los Comentarios de arriba nota un límite inferior de 15 en las tandas de 30 personas en tres mesas de 10, de modo que cada par está sentado uno al lado del otro.

Un límite superior de 29 para el número mínimo de asientos para lograr esto también se menciona en los Comentarios. Le damos una mejor cota superior mediante la construcción de un 18 solución de asientos.

Deje que los 30 participantes se dividen en seis subgrupos de 5 personas cada uno. Vamos a dedicar 3 asientos para cubrir todos los "intramuros" pares (pares dentro de un subgrupo) y 15 asientos para cubrir todos los "extramuros" pares (pares a través de distintos subgrupos).

Intramuros emparejamientos

Asignar la mitad de la circunferencia de una tabla a los asientos de un subgrupo de cinco personas. Cada par en este subgrupo pueden cubrir en tres tandas, como se ilustra con las siguientes etiquetas 1 a 5:

$$ \cdots 1 2 3 4 5 \cdots $$

$$ \cdots 3 1 5 2 4 \cdots $$

$$ \cdots 1 4 2 3 5 \cdots $$

Por supuesto, vamos a hacer esto para todos los seis subgrupos en paralelo, ya tenemos seis mitades de las tres mesas de trabajo. Para 3 asientos suficientes para cubrir todos los intramuros de emparejamientos.

Extramuros de emparejamientos

Para cubrir todos los pares entre los participantes en subgrupos, comenzar por partioning de vinculación entre los subgrupos. En la zona de estar, vamos suplente personas de dos grupos alrededor de cada mesa. Hay tres tablas, así que la partición de los 15 pares de subgrupos en cinco subconjuntos de 3 subgrupo pares.

Cada par de subgrupos pueden ser cubiertos con tres asientos como se ilustra con las etiquetas de 1 a 5 para uno de los subgrupos y de la a a la E para otro. Estas tres líneas son para envolver alrededor de una mesa:

$$ \cdots 1 A 2 B 3 C 4 D 5 E 1 \cdots $$

$$ \cdots 1 D 2 E 3 A 4 B 5 C 1 \cdots $$

$$ \cdots 1 B 2 C 3 D 4 E 5 A 1 \cdots $$

Así que todos los extramuros de emparejamientos que pueden ser cubiertos en tres veces cinco o 15 asientos.