domingo, 8 de julio de 2007

Reuniones de amigos

Enunciado

Antes de ponernos a hacer pruebas, vamos a hacer unos cálculos rápidos. Si son 7 amigos, cuando se sientan en una mesa circular, forman 7 parejas (cada uno con el de su derecha, ya que la pareja con el de su izquierda está contada al marcar al de la derecha de su compañero sentado a la izquierda). Reunirse 3 noches sin repetir pareja equivale a formar 21 parejas distintas (7 cada noche).

¿Cuántas parejas pueden, realmente, formarse con 7 personas? Si seleccionamos a una de las siete personas, tenemos 7 posibilidades, y 6 para seleccionar al acompañante. Sin embargo, hay que contar con que la pareja A-B es en realidad la misma que B-A, así que habrá que dividir entre 2 el número resultante, pues cada par de parejas lo contaremos dos veces. Así, podemos obtener 7*6/2 = 21.

Por tanto, si es posible reunirse de esa forma (que aún no lo sabemos), agotaremos todas las posibles parejas, de forma que debemos andar con mucho cuidado.

El número de 7 es manejable, de forma que procederemos a situarlos en la mesa con mucho cuidado de no repetir ninguna pareja. Supongamos que la posición desde A y siguiendo un sentido determinado en la mesa, es ABCDEFG, de forma que tenemos las parejas AB, BC, CD, DE, EF, FG y GA.

Empecemos a colocar los de la segunda noche. Junto a A no podemos sentar a B ni a G, empecemos por sentar a C, junto a C no podemos sentar a B ni a D, y así sucesivamente. Llegamos a una ubicación que puede ser, por ejemplo, ACEBGDF, que nos proporciona las parejas AC, CE, EB, BG, GD, DF y FA.

Para la tercera noche todas las parejas usadas están prohibidas, lo que nos debe dar una única ubicación válida para cada uno, puesto que sólo tendrá dos posibles vecinos de mesa (salvo cambio de sentido). Así, junto a A debe sentarse D y E, y si seguimos así, nos queda la ubicación ADBFCGE, que proporciona las parejas finales AD, DB, BF, FC, CG, GE y EA.

Como la segunda noche hemos usado una ubicación algo arbitraria, es posible que tengamos muchas soluciones más, pero está claro que eso alterará también la composición de la mesa de la tercera noche.

Actualizado

Ups propone en un comentario al enunciado una solución muy elegante. Tras mantener el orden de la primera noche, ABCDEFG, cada uno se sentará junto al que ocupaba dos sillas más a la derecha la segunda noche. Evidentemente, a su izquierda tendrá a quien estaba dos sillas a su izquierda, por lo que no repetirá pareja (ACEGBDF). La tercera noche, se sentará junto al que la primera noche estaba tres sillas a su derecha (o, equivalentemente, dos sillas a su izquierda la segunda noche, ADGCFBE). Tampoco, por razones evidentes, repetiremos compañero.

Mira el enunciado para leer el comentario original