Matemáticas y LaTeX 2005

El enigma de las Torres de Hanoi trata de un juego oriental muy antiguo, sin embargo fue presentado, a nivel mundial, en 1883 por el matemático francés Edouard Lucas, bajo el seudónimo de N. Lucas de Siam.

La leyenda que acompaña a este juego cuenta que en Benares (ubicado en la India), durante el reinado del Emperador Fo Hi, existía un templo con una cúpula que marcaba el centro del mundo. Los monjes del templo tenían que mover sesenta y cuatro discos sagrados de un emplazamiento a otro. Pero éstos eran tan frágiles que sólo se podía mover de uno en uno. Y además, tenían que tener cuidado al colocarlos, puesto que no se podía emplazar uno más valioso encima de otro de valor inferior. En este caso, el mencionado valor de los aros iba en proporción a su tamaño, cuanto más pequeño fuera el anillo menor era su valía. Para realizar los traslados de los referidos discos, solamente se disponía de otro lugar en el templo (además del de partida y del final) lo suficientemente sagrado como para que estas anillas pudieran ser depositadas en él. Así pues, los monjes comienzan el movimiento de éstas entre el montón inicial, el destino final y la posición intermedia, eso sí, manteniendo siempre el orden antes comentado (el más grande en el fondo y el más pequeño en la cima). La leyenda dice que antes de que los monjes logren reubicar todos los discos en la nueva localización, el templo volverá a convertirse en polvo y el mundo terminará.

El objetivo de este juego es colocar n discos en una barra de manera que el más grande quede en el fondo y el más pequeño en la cúspide. Para este fin, el jugador puede servirse la barra inicial o de partida, de la barra final, donde deben terminar los aros ordenados, y de una intermedia. El propósito del citado enigma es realizar esta ordenación con el menor número de movimientos posible. El acertijo con cuatro anillas se conoce como enigma de Reve.

Cabe señalar que este problema es equivalente a encontrar un trayecto de Hamilton en un n–hipercubo (Gardner 1957 - 1959).

Nota: se conoce como ‘trayecto de Hamilton’ al camino entre dos vértices de un gráfico, de manera que éste pase por cada vértice una sola vez.

Dadas tres barras y n discos, la secuencia

da el número del disco, desde uno hasta n, que debe ser movido en el k-ésimo paso. Para crear esta sencilla recurrencia iniciamos la lista con

para un solo aro y calculamos los siguientes movimientos con la fórmula recurrente:

Así pues, si tuviésemos cuatro discos, la tabla que generaría esta recurrencia sería la siguiente:

n ---> Sn
1 ---> 1
2 ---> 1,2,1
3 ---> 1,2,1,3,1,2,1
4 ---> 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1

Cuando el número de discos se incrementa, manteniendo las tres barras, se obtiene una sucesión infinita, cuyos primeros términos se muestran en la tabla anterior. Sorprendentemente, este es exactamente el código binario de la sucesión más uno. Este código se obtiene como la secuencia de los exponentes de las mayores potencias de dos que dividen al número pertinente. En este problema, la secuencia que nos da su solución es conocida como A001511. Aún más asombroso, el número de discos movidos después del k-ésimo paso es el elemento que necesitamos agregar o quitar en el sumando k-ésimo de la fórmula de Roser (Gardner 1988, Vardi 1991).

Como resultado del procedimiento anterior, el número de movimientos requerido para resolver el enigma con n anillas y tres pértigas viene dado por la fórmula recurrente:

tomando el primer elemento de la sucesión igual a uno, la recurrencia que se obtiene es la siguiente:

Los números con esta forma se conocen con ‘Números de Mersenne’.

Para tres barras, la prueba de que la solución mencionada arriba es mínima se puede realizar utilizando la correspondencia de Lucas que relaciona el triángulo de Pascal con el gráfico de Hanoi. Sin embargo, de los algoritmos que se conocen para cuatro pértigas aún no se ha podido probar que alguno de ellos sea mínimo.

Se puede construir un gráfico de Hanoi cuyos vértices correspondan a configuraciones válidas de las n torres de Hanoi. Éstos serán adyacentes si las ordenaciones correspondientes se pueden realizar mediante movimientos legales. En este caso, el problema se puede resolver utilizando el ‘código binario de Gray’.

En el siglo XX los matemáticos Poole y Rangel – Mondragón aportaron procedimientos implementados en el software Mathematica para resolver el problema que nos ocupa. El algoritmo de Poole trabaja con un configuración arbitraria de discos y proporciona la solución con un menor número de movimientos.

Trabajando con cuatro barras, los mínimos movimientos requeridos en función del orden de discos n = 1, 2, …, vienen dados por los números 1, 3, 5, 9, 13, 17…, que forman la secuencia A007664. Se especula que esta serie viene dada por la recurrencia:

tomando el primer elemento de la sucesión igual a uno, y x la solución entera positiva redondeada por defecto

Es decir,

De modo que la fórmula en forma explicita sería la siguiente: