Solución: Conversaciones durante la Última Cena

Solución: Conversaciones durante la Última Cena
Event type
Description

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.