Solución: Conversaciones durante la Última Cena

Publicamos la solución al Divertimento Conversaciones durante la Última Cena. Gracias a Gustavo Iacovino por la solución que ha aportado.

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:

Representamos a los comensales mediante los vértices de un grafo. Por ejemplo, para \(n=7\):

Se desea construir un grafo en el que cada vértice sea adyacente a todos los demás, es decir, esté unido a todos los demás. El primer día, cada comensal se sienta con las dos personas que tiene a distancia 1. El segundo día, con las dos personas que tiene a distancia dos, y así sucesivamente. En el caso en el que \(n=7\) es suficiente celebrar tres cenas:

En el caso general, la mayor distancia entre dos vértices es \(n/2\), si \(n\) es par, o bien \((n-1)/2\), si \(n\) es impar. Por tanto, las personas deberán citarse \(n/2\) noches, si \(n\) es par, o bien \((n-1)/2\) noches, si \(n\) es impar, para conseguir sentarse de forma que cada una de ellas tenga a sus lados a dos comensales distintos en noches diferentes.