La Torre de Hanoi y el fin del mundo

 La Torre de Hanói

Portada de la publicación original de E. Lucas

"En el gran templo de Benares, bajo la cúpula que marca el centro del mundo, se encuentran tres agujas de diamante. En una de ellas, en el momento de la creación, Dios colocó sesenta y cuatro discos de oro puro, el mayor abajo y los demás decreciendo hasta la cima. Es la Torre de Brahma.

Los monjes se turnan día y noche para trasladar la columna de la primera aguja de diamante a la tercera, siguiendo las reglas inmutables de Brahma: el monje no debe mover más de un disco a la vez, y solo puede colocar un disco en una aguja libre o sobre un disco de mayor tamaño.

Cuando los sesenta y cuatro discos hayan sido trasladados, el templo, los brahmanes y el universo entero desaparecerán en un instante." 

A diferencia de lo que sugiere su nombre, la Torre de Hanói no proviene de Vietnam. Fue inventada por el matemático francés Édouard Lucas en 1883 y lo comercializó bajo el seudónimo de "N. Claus de Siam" (un anagrama de Lucas d'Amiens). 

Obviamente, Hanói es la capital de Vietnam, mientras que Benares (Varanasi) está en el corazón de la India. Esa discrepancia geográfica es, precisamente, parte del "caos" creativo que Lucas provocó a propósito. El enunciado original  mezcla nombres y lugares sin mucho rigor geográfico, buscando simplemente un efecto exótico y místico que fascinara al público europeo de la época.   El nombre "Torre de Hanói" sonaba más moderno y comercial, mientras que la leyenda de Benares le daba el toque religioso y antiguo. 

La Realidad Matemática es que, como demostraremos más adelante, el número mínimo de movimientos necesarios para resolver una torre de \(64\) asciende a: $$2^{64} - 1= 18\;\;446\,744\,073\;\;709\,551\,615 \quad \text{movimientos}.$$ Si los monjes movieran un disco por segundo, sin equivocarse jamás, tardarían aproximadamente 585 mil millones de años en terminar. Teniendo en cuenta que nuestro Sol se apagará en unos 5 mil millones de años, estamos bastante seguros.

El Inventor detrás del mito

François Édouard Anatole Lucas (1842–1891), fue un brillante matemático francés, nacido en Amiens, cuya carrera osciló entre la rigurosidad académica y la pasión por la divulgación lúdica. Formado en la prestigiosa École Normale Supérieure, trabajó inicialmente como astrónomo en el Observatorio de París bajo la dirección de Urbain Le Verrier. Sin embargo, su mayor legado no estuvo en las estrellas, sino en la teoría de números y el desarrollo de métodos para identificar números primos, siendo su logro más famoso el test de Lucas-Lehmer.

A pesar de su capacidad para el análisis profundo, Lucas creía que las matemáticas debían ser accesibles y entretenidas. Fue un pionero de las "matemáticas recreativas", publicando una serie de volúmenes titulados Récréations mathématiques, donde exploraba juegos y acertijos que hoy son fundamentales en la enseñanza de la computación.

En el ámbito puramente teórico, su nombre quedó inmortalizado a través de las Sucesiones de Lucas, íntimamente relacionadas con la serie de Fibonacci. Estudió las propiedades de estos números y su aplicación en la primalidad, logrando demostrar en 1876 que el número de Mersenne $$M_{127} = 2^{127} - 1$$ es primo. Este récord de cálculo manual se mantuvo imbatible durante décadas, consolidando su reputación como uno de los teóricos más potentes de su siglo.

Su muerte fue tan inusual como algunos de sus acertijos. Durante un banquete en un congreso científico en Marsella, un camarero dejó caer un plato de porcelana; un fragmento cortó la mejilla de Lucas, provocándole una septicemia que terminó con su vida a los 49 años. Irónicamente, el hombre que calculó el tiempo necesario para el fin del mundo a través de sus discos de oro, no llegó a ver el siglo XX, dejando un vacío en la comunidad científica francesa.  

Ejemplo con tres discos

 

\(2^3-1=7\) movimientos.

El número mínimo de movimientos para una torre de \(n\) discos es \(M(n)=2^{n} - 1\)

 

La demostración la realizaremos por inducción completa.

Inicio de inducción. Si \(n=1\) el puzle se resuelve en \(M(1)=2^1-1=1\) paso.

Relación de inducción. Supongamos que para \(n=k\), donde \(k\) es un número natural. el puzle se resuelve en \(M(k)=2^k-1\) pasos, es decir:

 

 

Entonces para \(n=k+1\) el puzle se resuelve en \(M(k+1)=2^{k+1}-1= (2^{k}-1)+(1)+(2^{k}-1)\) pasos, en efecto:

Luego el enunciado es cierto para \(n=k+1\) y por el principio de inducción queda demostrado para todo \(n\) natural. 

 

La trascendencia de la Torre de Hanói

La pagoda de Tran Quoc en Hanói,
 que inspiró la torre de discos

La Torre de Hanói ha trascendido su origen como un simplepuzle del siglo XIX para convertirse en una de las herramientas pedagógicas más potentes de la ciencia moderna. Su importancia fundamental radica en ser el ejemplo sinificativo para ilustrar la recursividad, un concepto clave en informática donde un problema complejo se resuelve dividiéndolo en subproblemas más simples. En lugar de intentar mover todos los discos a la vez, el algoritmo enseña que para mover \(n\) discos, primero debemos saber cómo mover \(n - 1\), reduciendo la tarea a una serie de pasos lógicos e infalibles. En resumen, un ejemplo ilustrativo de. método de demostración matemática conocido como inducción completa

En el ámbito de la algoritmia, este puzle es esencial para comprender la complejidad exponencial. El número mínimo de movimientos necesarios para resolver una torre de $n$ discos se define mediante la función: \(M(n) = 2^n - 1\).

Esta fórmula demuestra visualmente cómo un pequeño incremento en los datos de entrada (añadir un solo disco) duplica el tiempo de procesamiento requerido. Es una lección vital para los ingenieros de software sobre los límites del cálculo y la necesidad de optimizar algoritmos antes de que el crecimiento de los datos los vuelva inmanejables para cualquier computadora actual.

Más allá del código, la Torre de Hanói tiene aplicaciones cruciales en la psicología cognitiva y la neurociencia. Se utiliza frecuentemente en pruebas de evaluación neuropsicológica (como la "Torre de Londres") para medir las funciones ejecutivas del cerebro, específicamente la capacidad de planificación, la memoria de trabajo y la resolución de problemas. Resolver el puzle exige que el sujeto anticipe movimientos futuros y mantenga reglas estrictas en su mente, lo que lo convierte en un diagnóstico perfecto para analizar el rendimiento de la corteza prefrontal humana.

 

---