Qué es la combinatoria y cómo consigue que las campanas nunca suenen en el mismo orden

Pero siempre quedarán problemas que podamos afrontar e, incluso, disfrutar con ellos. En el capítulo 6 del libro 'Viajes por el tiempo y otras perplejidades matemáticas' (1988) que reproduce su colaboración de noviembre de 1974 para la sección Mathematical Games de la revista 'Scientific American', Martin Gardner (1914-2010) recoge el problema planteado por Derrick Lehmer (1905-1991) en 1965, cuyo enunciado es básicamente el siguiente:

Un hotel tiene n habitaciones en línea, todas ocupadas. Cada día dos inquilinos de habitaciones contiguas intercambian sus habitaciones. ¿Es posible conseguir con este método que todos los inquilinos ocupen todas las habitaciones sin repetir ninguna?

Noticia Relacionada

¿Eres capaz de resolver el problema de las pastillas Juanola?

Pedro Alegría

Se trata de rellenar, con piezas de dominó, un tablero de ajedrez al que se le han eliminado dos esquinas diagonalmente opuestas

El planteamiento original es más entretenido y motivador porque se afirma que el gerente del hotel es un psicólogo que está investigando el efecto que produce el constante trasiego de habitaciones entre los clientes pero tiene gran corazón y, para minimizar las molestias, permite que el intercambio se realice entre habitaciones contiguas. En cualquier caso, el problema consiste en averiguar si hay algún método eficaz de conseguir que todos los inquilinos ocupen todas las habitaciones una sola vez.

Vale, el problema puede tener su interés pero, como es habitual, este interés se reduce a la comunidad matemática. ¿O quizá no? Resulta que, a principios del siglo XVII, se descubrió en Inglaterra que se podían modificar los ajustes de las campanas en un campanario, lo que permitía a los campaneros tener un control preciso del momento en que tañía cada campana y, así, hacerlas tocar en un determinado orden, manteniendo dicho orden o cambiándolo de forma precisa en el momento oportuno. Gracias a esta evolución, se puso de moda el reto de conseguir hacer sonar las campanas cambiando continuamente el orden, de modo que se lograran todas las combinaciones de sonidos, sin repetir ninguna y cambiando únicamente el orden de dos campanas en cada cambio. Por cierto, esta moda sigue vigente hoy en día en los campanarios del Reino Unido. Se pueden encontrar muchos vídeos explicando su funcionamiento y sirva este como muestra:

En el libro 'One hundred problems in elementary mathematics' (1958), Hugo Steinhaus (1887-1972) asegura que conoce un algoritmo válido. Un poco después, el algoritmo fue redescubierto independiente y casi simultáneamente por Hale Trotter (1962) y Selmer Johnson (1963). Sin embargo, no pueden considerarse los primeros en dar con la solución, pues Fabian Stedman y Richard Duckworth ya dieron una respuesta en el libro 'Tintinnalogia o el arte de tañer', nada menos que el año 1668, a propósito de la ya citada moda del cambio de tañido de campanas, pero adelantándose al mundo de las matemáticas.

Veamos en qué consiste el método de resolución del problema del hotel (o de las campanas), que es básicamente la aplicación de un procedimiento iterativo del que sólo ilustraremos los primeros pasos:

Si el conjunto está formado por dos números (o dos campanas), las dos permutaciones son 12 y 21, de modo que el problema está resuelto.

En el caso de tres números, se va colocando el 3 en las distintas posiciones de la primera de las dos permutaciones anteriores (empezando por el final) y de la segunda (empezando por el principio). Se obtiene así la secuencia

123, 132, 312, 321, 231, 213.

Para cuatro números, se van recorriendo las permutaciones anteriores, intercalando el 4 en la primera de ellas (empezando por el final), luego en la segunda (empezando por el principio), luego en la tercera (empezando por el final), y así sucesivamente. La secuencia es la siguiente:

1234-1243-1423-4123-4132-1432-1342-1324-3124-3142-3412-4312-4321-3421-3241-3214-2341-2431-4231-4213-2413-2143-2134.

Se obtienen las 24 permutaciones en 23 pasos, cumpliendo las restricciones del problema.

Una representación gráfica de las diferentes permutaciones nos da una idea mejor del método recursivo que se utiliza.

Como se puede observar, el último número se va intercalando entre las posiciones de cada permutación de los tres primeros números. Por eso, cada permutación de tres números se repite cuatro veces. Este mismo método se aplica para construir las permutaciones de cinco números y así sucesivamente. Se observa además, que la última permutación conduce de nuevo a la primera intercambiando solamente los dos primeros elementos.

Otra representación gráfica, como la de la imagen, permite destacar el carácter circular de las distintas permutaciones, donde los números se han sustituido por colores (en este caso, el color rojo se va intercalando entre los otros tres).

Una variante del problema plantea su relación con las figuras conocidas como permutaedros. De forma simplificada, podemos decir que un permutaedro de orden n es un poliedro donde los vértices representan todas las permutaciones de los n primeros números y las aristas son los caminos más cortos que los conectan entre sí. Además, las aristas conectan dos permutaciones que se diferencian únicamente en dos de sus posiciones. El problema del hotel de Lehmer se convierte ahora en el de encontrar un camino que recorra todos los vértices de modo que se cumplan las condiciones establecidas. Un trabajo del matemático holandés Tom Verhoeff de título 'The spurs of D.H. Lehmer' (2017) resuelve el problema.

Una vez resuelto el problema inicial, se han planteado distintas modificaciones. En el caso de las campanas, por ejemplo, si se pretende que ninguna campana pueda permanecer en la misma posición durante tres permutaciones consecutivas, ya no es posible el método anterior y se deben intercambiar más de dos campanas en cada cambio de sonido.

Aunque pueda sonar trivial y de poca trascendencia matemática, el problema tiene mucho interés pues, para un ordenador, supone un gran ahorro de tiempo y una mayor simplicidad intercambiar sólo dos datos adyacentes para recorrer todas las permutaciones posibles. Este sistema de describir las permutaciones de un conjunto está relacionado con los códigos de Gray, inventados por Frank Gray en 1974: un código de Gray es un sistema de numeración binaria en el que dos valores consecutivos se diferencian únicamente en un bit.

La ventaja de este sistema es su mayor facilidad en detectar y corregir errores (basta observar que, en el sistema binario posicional, hay números consecutivos que se diferencian en todas sus cifras, como son 2^n  1 y 2^n, el primero de ellos formado por n unos y el segundo es un uno seguido de n ceros). El uso más común de los códigos de Gray es el de corrección de errores en comunicaciones digitales como el de la televisión por cable aunque también son importantes para la resolución de problemas de matemática recreativa, como el de las torres de Hanoi y el de los anillos de Cardano.

Como curiosidad, citaremos dos aplicaciones del problema del hotel de Lehmer a situaciones concretas: la ceremonia de apertura de la novena olimpiada europea femenina de matemáticas, celebrada de forma virtual –por motivos obvios– en abril de 2020 tiene como hilo conductor una secuencia de cambios de permutaciones

(En el vídeo de arriba se puede seguir el desarrollo de la ceremonia);

por último, el espectáculo coreográfico que se desarrolla en este video también está basado en el mismo problema.

El ABCdario de las Matemáticas es una sección que surge de la colaboración con la Comisión de Divulgación de la Real Sociedad Matemática Española (RSME).

SOBRE EL AUTOR

Pedro Alegría

Universidad del País Vasco/Euskal Herriko Unibertsitatea.Comisión de divulgación de la RSME.