El Fin Del Mundo: Las Torres De Hanoi

La presente entrada «El Fin Del Mundo: Las Torres De Hanoi» es otra de las historias que nos van acercando al maravilloso mundo de las matemáticas. Nos adentramos en el juego que ganó popularidad gracias a la invención de su historia por parte de su creador, historia que tiene connotación de leyenda por el contexto en que se desarrolla y sus protagonistas.

Al igual que en historias  anteriores, que traen inmersos trucos numéricos, como el propuesto en Carl El Niño Genio. Trucos que permitieron resolver algunos de los problemas más antiguos de los Egipcios, como en Tales de Mileto y La Gran Pirámide. Y que permitieron acercar los números desde la India hasta nosotros. Iniciemos en esta oportunidad con una historia más de esta serie que desde entradas anteriores hemos ido abordando y que han tenido gran aceptación entre nuestros lectores…

El Fin Del Mundo: Las Torres De Hanoi

Durante muchos años y en diferentes culturas se han divulgado varias leyendas y creencias sobre el fin del mundo.

Una vieja leyenda india cuenta que cuando el mundo fue creado, Dios ubicó sobre la tierra tres varillas de diamante y en una de ellas puso 64 discos de oro, en orden de mayor a menor diámetro, de manera que el más pequeño quedará en la parte de arriba de la pila. También creó un gran templo que tenía una hermosa cúpula señalando el centro del mundo. En ese templo, ubicó unos monjes cuya tarea era trasladar los 64 discos a otra de las agujas, siguiendo ciertas leyes:

• Sólo los monjes del templo pueden mover los discos.
• Todos los días se moverá un disco.
• No se puede mover más de un disco al día.
• No se puede situar un disco encima de otro de menor tamaño.

La leyenda también dice que la torre, el templo y el mundo acabarán cuando los monjes hayan terminado su tarea.

La pila con los 64 discos se conoce como la Torre De Brahma porque en el hinduismo Brahma es el Dios creador.

Siguiendo las reglas indicadas, los monjes se demorarían en mover los 64 discos mas de 500 billones de siglos. Es decir que, según la leyenda, el fin del mundo está todavía my, muy lejos.

Un matemático francés llamado Edward Lucas inventó un juego similar al de la leyenda hacia el año 1883, que tiene tres varilla verticales y unos discos de madera de diferentes tamaños. El juego consiste en pasar todos los discos de una varilla a otra, dejándolos en el mismo orden inicial. Hay que hacerlo en el menor número posible de movimientos, moviendo sólo un disco a la vez y sin colocar uno sobre otro de menor tamaño. Entre más discos tenga el juego, mayor es el número de movimientos y más difícil es resolverlo. Este juego se conoce como Las Torres De Hanoi.

Y ahora, ¿Qué piensas?

Antes de proceder al cómo se resuelve, te propongo el siguiente ejercicio. El objetivo es que tu seas quien determine el patrón presente en la solución:

1. Busca tres monedas de diferentes tamaños y organízalas una sobre otra de mayor a menor. Coloca tres pedazos de cartulina y comienza a mover las monedas, siguiendo las reglas del juego, de tal forma que al final, las monedas queden en la tercera cartulina. ¿Cuál es el menor número de movimientos que se necesitan?
2. Ahora consigue otra moneda de diferente tamaño y determina cuál es el número mínimo de movimientos para pasar las cuatro monedas a la tercera cartulina.
3. ¿Y cuántos movimientos se requieren para mover cinco monedas?

Te propongo practicar los movimientos para que encuentres el patrón en el siguiente applet. Recuerda seguir las reglas: NO puedes mover más de un disco a la vez y NO se puede situar un disco encima de otro de menor tamaño.

Si en lugar de mover un disco cada día, los monjes pudieran mover un disco cada segundo, ¿terminarán antes de un año? si no has encontrado el patrón, no te preocupes, vamos a ello:

Antes de iniciar es necesario hacer un par de aclaraciones: Primero, las tres varillas (torres) serán la de origen (donde están los anillos), la de destino (donde van a acabar), y la intermedia. Segundo, para resolver una Torre de Hanoi debemos tener en cuenta que, el número mínimo de movimientos depende  siempre del número de discos iniciales. Por lo tanto, si tenemos “n” discos iniciales, los movimientos mínimos necesarios para terminar el juego serían:

Claramente se ve en los primeros pasos que la fórmula es cierta:

• Si n=0, Sin movimientos
• Cuando n=1, entonces mover el único disco de la varilla de Origen a la de Destino
• n=2, 3 movimientos
• n=3, 7 movimientos
• n=4, 15 Movimientos
• n=5, 31 movimientos

Retomando, si la leyenda de los monjes fuera cierta, ¿cuándo acabaría el mundo?.  Veamos:

Bajo esta fórmula, los 64 discos acabarían en el lugar adecuado en nada más y nada menos que 18.446.744.073.709.551.615 segundos. Si los monjes fuesen capaces de realizar un movimiento cada segundo, el tiempo necesario para trasladar la columna sería, aproximadamente, de 585.000.000.000 años, que viene a ser más de cien veces la edad actual de nuestro sol.

¿Cómo se resuelve La Torre de Hanoi?

Vamos a resolver Iterativamente La Torre de Hanoi, para ello recordemos lo que es una Iteración. Una operación iterativa es la que repite un proceso durante un número determinado de veces (iteraciones), dependiendo de los parámetros definidos inicialmente. Normalmente la salida de una iteración del proceso se utiliza como punto de inicio para la siguiente iteración. Cada paso origina el paso siguiente. El proceso continúa hasta que se alcanza una meta determinada y el proceso termina.

El truco está en el disco más pequeño. 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.

La clave está en decidir a cuál de las dos varillas posibles se desplazará el disco pequeño (Intermedia o Destino), en cada paso impar. Además, Todo va a depender del número de discos iniciales que tengamos. En este orden de ideas, se nos presentan dos casos. Trataré de explicarlo de la manera más clara posible:

Cuando el número inicial de discos es impar

El algoritmo óptimo, el que menor número de movimientos requiere, para mover una torre de n discos de la primera varilla a la tercera es el siguiente:

• El primer movimiento debe ser «colocar el disco más pequeño en la varilla de Destino».
• En cada paso impar se le mueve  a la siguiente fila a su izquierda o a la varilla Destino (si está en la varilla de Origen).
• La secuencia debe ser: destino, intermedia, origen y, se repite, destino, intermedia, origen.

Ejemplo

Si jugamos con 3 discos, según la fórmula, el número mínimo de movimientos para completar el juego serían 7. Veamos:

Llevamos las 3 fichas de la varilla «Origen» a la varilla «Destino», empleando sólo 7 movimientos y siguiendo la secuencia de movimientos: destino, intermedia, origen … destino, intermedia, origen (sucesivamente). Observemos cómo se realizarían los movimientos mencionados:

Cuando el número inicial de discos es par

El algoritmo óptimo, el que menor número de movimientos requiere, para mover una torre de n discos de la primera varilla a la tercera es el siguiente:

• El primer movimiento debe ser «colocar el disco más pequeño en la varilla Intermedia».
• En cada paso impar se le mueve a la siguiente fila a su derecha o a la varilla Origen (si está en la varilla de destino).
• La secuencia debe ser: Intermedia, destino, origen y, se repite, Intermedia, destino, origen.

Ejemplo

Si jugamos con 4 discos, según la fórmula, el número mínimo de movimientos para completar el juego serían 15. Veamos:

Llevamos las 4 fichas de la varilla «Origen» a la varilla «Destino», empleando sólo 15 movimientos y siguiendo la secuencia de movimientos: Intermedia, destino, origen … Intermedia, destino, origen (sucesivamente). Observemos cómo se realizarían los movimientos mencionados:

Finalmente, les presento el video que nuestro amigo Pedro Neves realizó mostrando los procesos para solucionar La Torre De Hanoi hasta con 8 discos.

Espero que esta historia haya sido de tu agrado. Anímate a aprender y compartir tus experiencias. Salón Matemático agradece y estará atento a tus comentarios.  Haz parte de nuestra comunidad en redes sociales, síguenos en FaceBook, Twitter y en nuestro canal de YouTube. No olvides Suscribirte al boletín de noticias para estar al tanto de nuestro contenido. Comparte nuestra web a tus contactos. ¡Feliz Aprendizaje!