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.
