Publicamos una nueva solución para el Divertimento Conversaciones durante la Última Cena. La solución publicada originalmente contenía un error: con el método propuesto, para 9 personas se necesitan 3 mesas distintas.
Divertimento:
Un grupo de \(n\) personas acuerdan cenar juntas en diferentes noches. En cada una de ellas se sientan alrededor de una mesa redonda de modo que cada persona tiene a sus dos lados comensales distintos en cenas diferentes. Si todos quieren sentarse junto a todos los demás, ¿Cuántas noches deberán citarse para cenar?
Solución:
Solución enviada por Juan Arias de Reyna.
Probaremos que si \(n=2m+1\) o \(n=2m\), entonces \(m\) cenas seran suficientes y necesarias para que dos comensales cualquiera se sienten juntos alguna noche.
Proposición: Si \(n=2m+1\) es impar o bien \(n=2m\) es par, se necesitan al menos \(m\) cenas para conseguir que todas las parejas se sienten alguna noche juntas.
Nota: Pensamos aquí que \(m \geq 1\). En el caso de 1 persona podemos decir que no necesita ninguna noche, porque no hay parejas.
Demostración: Si hay \(n\) comensales y se sientan en una mesa redonda, habrá \(n\) parejas que ya han conseguido el objetivo en una cena. El número total de parejas es \({{n}\choose{2}}=\frac{n(n-1)}{2}\). Si \(K\) cenas son suficientes, entonces a lo mas tenemos \(nK\) parejas que se han sentado juntas, luego debe ser
$$Kn\geq \frac{n(n-1)}{2}, \qquad K\ge \frac{n-1}{2}.$$
Si \(n=2m+1\) es impar tendremos que \(K\ge m\) y si es par \(n=2m\) tendremos \(K\ge m-\frac12\). Es decir, que \(K\ge m\), ya que es entero.
Proposición: Si \(n=2m+1\) es impar o bien \(n=2m\) es par, \(m\) cenas son suficientes para conseguir que todas las parejas se sienten alguna noche juntas.
Demostración: En primer lugar describimos la disposición en que tienen que sentarse los comensales cada una de las \(m\) noches para conseguir su objetivo. Atenderemos primero al caso \(n=2m\) de un número par de comensales. Asignamos a cada comensal un número de \(0\) a \(n-1\). Es conveniente pensar a los comensales como elementos del anillo \(\mathbb{Z}/(n\mathbb{Z})\) de los restos módulo \(n\).
En la primera noche disponemos los comensales en la forma
$$\begin{array}{cccccccccccccccccccccccccccc}
0 & 1 & n-1 & 2 & n-2 & 3 & n-3 & \dots & m-1 & m+1 & m \\
\end{array}$$
(recordar que \(n=2m\)).
Por ejemplo, cuando \(m=8\), los comensales se sentaran en la disposición
\[\begin{array}{ccccccccccccccccccccccccc}
0 & 1 & 7 & 2 & 6 & 3 & 5 & 4 \\
\end{array}\]
La disposición en cada noche se obtiene de la anterior sumando una unidad (módulo \(n\)) a los comensales de la noche anterior, hasta llegar a \(m\) noches. Así, en el caso de \(8\) comensales, la solución será
\[\begin{array}{ccccccccccccccccccccccccc}
0 & 1 & 7 & 2 & 6 & 3 & 5 & 4 \\
1 & 2 & 0 & 3 & 7 & 4 & 6 & 5 \\
2 & 3 & 1 & 4 & 0 & 5 & 7 & 6 \\
3 & 4 & 2 & 5 & 1 & 6 & 0 & 7
\end{array}\]
que se puede comprobar que son suficientes en este caso.
Volvamos al caso general. Si agrupamos los comensales dispuestos como en la primera noche en la forma
\[0, (1,n-1), (2,n-2), (3,n-3), \dots (m-1,m+1), m ,\]
vemos que cualquier pareja \((a,b)\in(\mathbb{Z}/(n\mathbb{Z}))^2\) tal que \(a+b=0\) se habrá sentado la primera noche uno al lado del otro (teniendo en cuenta que las parejas \((m,m)\) o \((0,0)\), que cumplen la condición \(m+m=0\), no son parejas). Estas son en total \(m-1\) parejas.
Aparte de estas en la primera noche se sientan juntas las parejas \((a,b)\in(\mathbb{Z}/(n\mathbb{Z}))^2\) que cumplen \(a+b=1\), como vemos en el siguiente diagrama:
\[(0,1), (n-1,2), (n-2,3), \dots, (m+1,m).\]
En total son \(m\) parejas. Luego en la primera noche todas las parejas \((a,b)\) que sumen \(0\) o \(1\) se han sentado juntas. En la segunda noche se habrán sentado juntas todas las parejas de la forma \((a+1,b+1)\), es decir, todas las parejas que sumen \(2\) o \(3\). En la tercera noche se sientan juntas las parejas que sumen \(4\) o \(5\). Así hasta que en la noche \(m\)-ésima se sienten juntas todas las parejas \((a+m-1, b+m-1)\), esto es todas las parejas que sumen \(a+b+2m-2\). Por tanto todas las parejas que sumen \(n-2\) o \(n-1\). Pero dada cualquier pareja \((a,b)\) su suma será \(a+b=0\), \(1\), \(2\), \(\dots\), o \(n-1\). Y por tanto se habrán sentado juntas en alguna de las \(m\) noches. Esto acaba la prueba en el caso par.
Para resolver el caso \(n+1=2m+1\) consideramos un comensal especial. Pensemos en la Última cena: Jesucristo con los doce apóstoles. Asignamos como antes los apóstoles al grupo aditivo \(\mathbb{Z}/(12\mathbb{Z})\) y designemos a Jesucristo como el comensal \(\infty\). La primera noche los sentamos en la forma
\[\infty\quad 0\quad 1\quad 11\quad 2\quad 10\quad 3\quad 9\quad 4\quad
8\quad 5\quad 7\quad 6\]
Y seguimos la misma regla que antes sumamos una unidad a cada uno para obtener la posición en la siguiente noche. Esto significa que Jesucristo se sienta en un lugar fijo, la presidencia de la mesa. Como la mesa, ahora sí, es redonda, Jesucristo está sentado el primer día entre \(0=\)Juan y \(6=\)Judas. Eso implica que los siguientes días estará sentado entre \(1\) y \(7\), entre \(2\) y \(8\), \(\dots\), y entre \(5\) y \(7\). Luego todos se habrán sentado alguna noche con Jesucristo. Este razonamiento vemos que es general. El presidente se sienta la primera noche en medio de \((0,m)\), y en las sucesivas en medio de \((1, m+1)\), \((2, m+2), \dots, (m-1,n-1)\) y se habrá sentado con todos.
Dejar una contestacion