Torres de Hanói
El objetivo del juego es trasladar la pila a otro de los postes siguiendo ciertas reglas, como que no se puede colocar un disco más grande encima de un disco más pequeño.
Para realizar este objetivo, es necesario seguir tres simples reglas: Existen diversas formas de llegar a la solución final, todas ellas siguiendo estrategias diversas.
Se cuenta una historia sobre un templo en la India en Kashi Vishwanath que contiene una gran sala con tres postes gastados por el tiempo, rodeada de 100 discos dorados.
Se puede decir que el templo o monasterio se encuentra en diferentes partes del mundo, incluidos Hanói, Vietnam, y puede estar asociado con cualquier religión.
En algunas versiones, se introducen otros elementos, como el hecho de que la torre fue creada en el comienzo del mundo, o que los sacerdotes o monjes solo pueden hacer un movimiento por día.
Finalmente, el disco n.o 1 regresa de la varilla destino a la origen (sin pasar por la auxiliar), y así sucesivamente.
Este problema se suele plantear a menudo en programación, especialmente para explicar la recursividad.
Otra manera de resolver el problema, sin utilizar la recursividad, se basa en el hecho de que para obtener la solución más corta, es necesario mover el disco más pequeño en todos los pasos impares, mientras que en los pasos pares solo existe un movimiento posible que no lo incluye.
Son las siguientes: Tengamos un plato de Hanói con tres varillas colocadas tal que la primera contenga los n discos ordenados y las otras dos varillas no contengan nada.
Empecemos definiendo el ejercicio más básico, tenemos un solo disco, por tanto el movimiento del primer plato al último es 1 solo paso.
Para la resolución de este ejercicio se pueden aplicar dos caminos diferentes.
La resolución de la ecuación en diferencia general que nos permitirá hallar las raíces de un polinomio y sus coeficientes para calcular posteriormente una función f(n) que nos devuelva un número exacto de movimientos dados para n discos o aplicar recurrencia para tratar por intuición el resultado final: Tengamos un estado
que denota la cantidad de movimientos a realizar para n discos.
Para la inducción débil partimos de la misma premisa que en la fórmula general pero en este paso utilizaremos otro método de verificación que en casos más sencillos como este ejercicio puede resultar más útil pero no es válido para todo tipo de sucesiones o ecuaciones en diferencia.
y previamente debido a la anterior demostración sabemos que para el movimiento
El siguiente paso es el deductivo y es el más importante pues una mala deducción llevara a un resultado.
En último caso podemos aplicar inducción débil para verificar que el resultado obtenido es el correcto:
Llegamos a la conclusión que ambos métodos son igualmente válidos para obtener la cantidad de movimientos necesarios para n discos dados ordenados en la primera varilla.
Una curiosa generalización del objetivo original del rompecabezas es comenzar desde una configuración dada de los discos, donde todos los discos no están necesariamente en el mismo poste, y llegar en un número mínimo de movimientos a otra configuración determinada.
En general, puede ser bastante difícil calcular una secuencia más corta de movimientos para resolver este problema.
Andreas Hinz propuso una solución y se basa en la observación de que, en la secuencia más corta de movimientos, se debe mover el disco más grande (obviamente, pueden ignorarse todos los discos más grandes que ocuparán el mismo poste tanto en la configuraciones inicial como en la final) se moverá exactamente una vez o exactamente dos veces.
Las matemáticas relacionadas con este problema generalizado se vuelven aún más interesantes cuando se considera el número promedio de movimientos en la secuencia más corta de movimientos entre dos configuraciones de disco iniciales y finales que se eligen al azar.
Hinz y Chan Hat-Tung descubrieron de forma independiente[5][6] (véase también [7]: Chapter 1, p. 14 ) que la cantidad promedio de movimientos en una torre de n discos viene dada por la siguiente fórmula exacta: Tenga en cuenta que para n lo suficientemente grande, solo el primer y el segundo término no convergen a cero, por lo que obtenemos un expresión asintótica:
Así, intuitivamente, se podría interpretar que la fracción de
representa la relación del trabajo que se debe realizar al pasar de una configuración elegida al azar a otra configuración elegida al azar, en relación con la dificultad de tener que cruzar la ruta de longitud "más difícil"
que implica mover todos los discos de un poste a otro.
Henry Dudeney en su libro The Canterbury Puzzles (1907) propuso una variante (llamada «Problema del almojarife» o The reve's puzzle) que usa cuatro postes en lugar de tres.
[9] En 1939, J. S. Frame y B. M. Stewart propusieron —en forma independiente— un algoritmo que resuelve el problema, dado un parámetro i: Y demostraron que, si n es igual al número triangular tk, la elección óptima para i es justamente k, y si tk – 1 < n < tk, tanto k – 1 como k lo son.
Nótese que se está hablando del valor óptimo para este algoritmo particular; encontrar el número mínimo de movimientos en el caso general es, todavía, una cuestión abierta.
Sin embargo, para n menor o igual a 30 discos se ha verificado que el algoritmo de Frame-Stewart es, efectivamente, óptimo.
