Torres de Hanoi

11 abr 2010



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.

Resolución: el problema de las Torres de Hanoi es curioso porque su solución es muy rápida de calcular, pero el número de pasos para resolverlo crece exponencialmente conforme aumenta el número de discos. 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 sólo existe un movimiento posible que no lo incluye. El problema se reduce a decidir en cada paso impar a cuál de las dos pilas posibles se desplazará el disco pequeño:

El algoritmo en cuestión depende del número de discos del problema. Si inicialmente se tiene un número impar de discos, el primer movimiento debe ser colocar el disco más pequeño en la pila destino, y en cada paso impar se le mueve a la siguiente pila a su izquierda (o a la pila destino, si está en la pila origen).

La secuencia será DESTINO, AUXILIAR, ORIGEN, DESTINO, AUXILIAR, ORIGEN, etc.
Si se tiene inicialmente un número par de discos, el primer movimiento debe ser colocar el disco más pequeño en la pila auxiliar, y en cada paso impar se le mueve a la siguiente pila a su derecha (o a la pila origen, si está en la pila destino).
La secuencia será AUXILIAR, DESTINO, ORIGEN, AUXILIAR, DESTINO, ORIGEN, etc.

Jugar a las Torres de Hanoi online:


http://www.cheesygames.com/hanoi

http://www.ematematicas.net/torre.php


Fuentes consultadas:

http://matelatex.blogcindario.com/


http://www.rodoval.com/heureka/hanoi/


http://www.aulademate.com/index.php


0 comentarios: