Torres de Hanói

Las Torres de Hanoi es un clásico rompecabezas matemático que consiste en tres pelucas y un conjunto de discos de diferentes tamaños. Al principio, todos los discos se apilan en una peluca en orden decreciente de tamaño, con el más grande en la parte inferior y el más pequeño en la parte superior. El objetivo es mover toda la pila a otra peluca, siguiendo reglas estrictas sobre cómo se pueden mover los discos. El número mínimo de movimientos requeridos para resolver un rompecabezas con discos N es 2^N - 1.

Reglas

1. Tres pegs (o torres) están dispuestos lado a lado.
2. Un número de discos de diferentes tamaños comienzan apilados en un peg, ordenado de mayor (abajo) a menor (top).
3. Sólo un disco se puede mover a la vez.
4. Cada movimiento consiste en tomar el disco superior de un peg y colocarlo encima de otro peg.
5. Un disco más grande puede nunca ser colocado en la parte superior de un disco más pequeño.
6. El objetivo es mover toda la pila de la peluca inicial a la peluca objetivo.

Estrategias

• Enfoque recursivo: Para mover discos N de peg A a peg C utilizando peg B como auxiliar: primero mover los discos N-1 superior de A a B, luego mover el disco más grande de A a C, luego mover los discos N-1 de B a C.
• Patrón Iterante**: En movimientos numerados, mueva el disco más pequeño. En movimientos incluso numerados, hacer el único movimiento legal que no implica el disco más pequeño. El disco más pequeño siempre se mueve en la misma dirección de rotación (A→B→C→A para un número impar de discos, A→C→B→A incluso).
• Cuento binario: La secuencia de movimientos corresponde al conteo binario. El disco para mover el paso K está determinado por la posición del bit más bajo fijado en la representación binaria de K.
• Iniciar Small: Practicar con 3 discos (7 movimientos) antes de intentar números mayores. El patrón se vuelve intuitivo una vez que lo vea repetido.
• Frame-Stewart Algorithm: Para variantes con más de 3 pegs, el algoritmo Frame-Stewart ofrece soluciones óptimas conjeturadas, aunque la optimización sólo se ha probado para 4 pegs.

Las Torres del rompecabezas Hanoi fueron inventadas en 1883 por el matemático francés Edouard Lucas, quien lo publicó bajo el seudónimo "Profesor N. Claus de Siam" (un anagrama de "Lucas d'Amiens"). El rompecabezas fue vendido como un juguete con una leyenda afirmando que en un templo en Benares (Varanasi), India, los sacerdotes Brahmin estaban trabajando en una versión con 64 discos dorados en agujas de diamante. Según la leyenda, cuando los sacerdotes completaron el rompecabezas, el mundo terminaría. A la velocidad óptima de un movimiento por segundo, la versión de 64 discos requeriría 2^64 - 1 movimientos, aproximadamente 585 mil millones de años, mucho más que la edad estimada del universo.

El rompecabezas rápidamente se convirtió en un básico de las matemáticas recreativas. Fue uno de los primeros puzzles que se analizaron a fondo utilizando el concepto de recursión, y sigue siendo uno de los ejemplos más importantes en la educación informática para enseñar algoritmos recursivos, inducción matemática y complejidad algorítmica.

Más allá de su papel como herramienta de enseñanza, las Torres de Hanoi tiene profundas conexiones con otras áreas de matemáticas. El espacio de estado del rompecabezas forma un gráfico triángulo Sierpinski, que lo conecta a la geometría fractal. El rompecabezas también tiene aplicaciones en esquemas de rotación de respaldo (la estrategia de copia de seguridad "Tower of Hanoi"), códigos Gray y el análisis de ciertos algoritmos de clasificación.

Las variantes del rompecabezas incluyen el problema de Frame-Stewart (utilizando 4 o más pegs), variantes coloreadas donde los discos deben terminar en un arreglo específico, y versiones bicolor donde se deben separar dos conjuntos entrelazados de discos. El rompecabezas se ha adaptado en numerosos videojuegos, apareciendo como un mecánico de rompecabezas recurrente en los juegos de aventura, RPGs y compilaciones de rompecabezas. Fue presentado prominentemente en el Doctor Who historia "El Toymaker Celestial" de 1966 y ha aparecido en películas como "Elevación del Planeta de los Apes" (2011) como una prueba de capacidad cognitiva.