TORRES DE HANOI
Bloque. Taller de Matemáticas
 

LA LEYENDA DE LAS TORRES DE HANOI
Dice la leyenda que, al crear el mundo, Dios situó sobre la Tierra tres varillas de diamante y sesenta y cuatro discos de oro. Los discos son todos de diferente tamaño e inicialmente fueron colocados en orden decreciente de diámetros sobre la primera de las varillas. También creó Dios un monasterio cuyos monjes tienen la tarea de trasladar todos los discos desde la primera varilla a la tercera. La única operación permitida es mover un disco de una varilla a otra cualquiera, pero con la condición de que no se puede situar encima de un disco otro de diámetro mayor. La leyenda dice también que cuando los monjes terminen su tarea, el mundo se acabará.

A la sombra de esta leyenda se creó un juego de niños llamado, naturalmente, "Las Torres de Hanoi". No es necesario tener dicho juego para poder jugar con él, unas cuantas monedas de distintos tamaño nos servirían o una simulación por ordenador. Esto último es lo que hace la siguiente escena.

 

Número de Discos:
Para mover un "disco" de una torre a otra se pulsa sobre el botón adecuado.

Si intentamos hacer un movimiento no permitido (mover desde una torre vacía o querer poner un disco de diámetro mayor sobre uno más pequeño) un de mensaje de aviso aparecerá. No conviene empezar con un número de discos superior a cuatro. Y el caso de 7 discos es mejor no intentarlo si no se tiene un buen método para hacerlo. Todos los discos deben pasarse a la varilla "DERECHA".

Suponemos que ya nos hemos familiarizado con el juego y que hemos resuelto el pasatiempo con el menor número de movimientos posibles (un mensaje de felicitación nos aparece en tal caso). Nos proponemos sacar conclusiones sobre el número de movimientos mínimo para un número determinado de discos, y así, averiguar cuánto tiempo queda para el fin del mundo según esta leyenda. Empecemos rellenando una tabla como la que sigue:

Número de Discos: 1 2 3 4 5 6 7
Número de Movimientos: 1 3          

Para poder continuar, tenemos que tener rellena con los datos correctos la tabla anterior, al menos, para 1, 2, 3 y 4 discos; y mejor si también se tiene para 5.


NÚMERO DE MOVIMIENTOS EN FUNCIÓN DEL NÚMERO DE DISCOS
De ahora en adelante, llamaremos mk al número de movimentos mínimos necesarios para pasar k discos de la torre "IZQUIERDA" a la torre "DERECHA". Así tenemos que:

m1 = 1, m2 = 3, m3 = 7, m4 = 15, m5 = 31

Es fácil observar un par de cosas:

  • mk = 2*mk-1 + 1. Por ejemplo: m5 = 2*m4 + 1. Si hemos trabajado suficientemente con la escena y hemos pensado cómo conseguimos pasar los discos a la torre de la derecha, nos habremos dado cuenta que, utilizando como ejemplo 4 discos: primero pasamos los tres de arriba a la torre "CENTRO" utilizando para ello 7 movimientos (m3); luego pasamos el disco mayor a la torre "DERECHA", 1 movimiento; por último pasamos los tres discos de "CENTRO" mediante 7 movimientos (m3). En total, para 4 discos, hemos necesitado: m3 + 1 + m3 = 2*m3 + 1 = m4.
  • mk = 2k - 1. Si se conoce el método de inducción, puede hacerse una demostración fácil de esta fórmula utilizando la fórmula anterior.

Ya tenemos una fórmula que nos permite calcular el número de movimientos necesarios para trasladar todos los discos desde la torre "IZQUIERDA" a la torre "DERECHA". Vamos a utilizarla para averiguar cuanto queda hasta el final de los tiempos según la leyenda de la Torres de Hanoi.

Como son 64 discos, el número de movimientos es 264 - 1 = 18446744073709551615. Si suponemos que los monjes tienen la suficiente habilidad como para hacer un movimiento en un segundo, en un día harán 60*60*24 movimientos. Y en un año de 365 días: 60*60*24*365. Dividimos el número de movimientos por el resultado de la operación anterior y nos debe dar, aproximadamente, medio billón de años. Sólo falta averiguar cuantos años se estiman que el hombre lleva sobre la tierra y sabremos el tiempo que le queda sobre ella.


SOLUCIÓN DEL JUEGO
Puede que alguien no haya conseguido trasladar todos los discos desde la torre "IZQUIERDA" a la torre "DERECHA", o sencillamente piense que es mejor que sean los monjes los que se dediquen a tal menester. Pues bien, para esos (y para todos los demás) vamos a ver cómo lo hace el "Descartes".

 

Número de Discos:

El control numérico mseg (milisegundos) nos permitirá controlar la pausa entre un movimiento y otro. Sólo he puesto hasta diez discos, pues, como vimos en el apartado anterior el número de movimientos aumenta de forma exponencial.

Por cierto, no está nada claro qué fue primero: el juego o la leyenda. He oído rumores de que el que inventó el juego, también inventó la leyenda. ¿Álguien me puede sacar de esta duda?


PARA PENSAR MÁS
Un juego como este puede dar más de sí, desde el punto de vista matemático. Y, para ver que esta afirmación es cierta, a continuación van unas cuestiones para su estudio, las cuales puede que no sean fáciles de contestar.

Para fijar ideas supondremos que estamos jugando con 5 discos que están numerados desde el 0 al 4; siendo el 0 el de mayor diámetro, es decir, el que se encuentra, al principio, en la base de la torre "IZQUIERDA". Las torres no se llamarán "IZQUIERDA", "CENTRO" y "DERECHA", sino 0, 1 y 2, respectivamente. También supondremos numerados los movimientos desde el 1 en adelante, en este caso, desde 1 a 31; siendo el 1 el primer movimiento que realizamos. Y sin más preámbulo, aquí están las cuestiones:

  1. ¿Qué disco se mueve en los movimientos impares? ¿Cuántas veces movemos este disco?
  2. El disco 3, ¿en qué movimientos se mueve? ¿Cuántas veces lo movemos?
  3. Los discos 2, 1, 0, ¿en qué movimientos se mueven? ¿Y cuántas veces lo hace cada uno?
  4. Llamamos nk al número de veces que se mueve el disco k. La sucesión de números n0, n1, n2, n3, n4 tiene un nombre particular en Matemáticas, ¿cuál?
  5. En el movimiento 3 el disco 4 se mueve a la torre 1. Y en el 5, ¿a qué torre? Y en el 7, 9, ...
  6. Plantearse y responder preguntas análogas a la anterior para los discos 3, 2, 1 y 0.
  7. En el movimiento 12, ¿qué disco se mueve y a qué torre? ¿en qué torre se encontraba dicho disco?

Todas estas preguntas van encaminadas a encontrar una relación entre movimiento, disco y torre. O sea, sabiendo en qué movimiento nos encontramos, hallar qué disco hay que mover y a qué torre hay que moverlo.

Una tabla como la siguiente:

Nº de Mov.: 1 2 3 4 5 6 7 8 9 ...
Nº de Disco: 4 3 4              
Nº de Torre: 2 1 1              

nos ayudará a resolver las cuestiones. A partir de ella se puede crear otra tabla donde sólo aparezca lo referente al disco 4, otra para el disco 3, etc.

El botón nos servirá tanto para comprobar los valores de la tabla como para echarnos una mano en su confección.

En la tabla anterior, cuando esté completa, si elimináis todas las columnas correspondientes a números de movimientos impares y después dividís todos los elementos de la fila de movimientos entre 2, ¿a qué corresponde la tabla resultante?

Generalizar todo lo que se ha observado para 5 discos es el final del proceso matemático, lo cual puede ser aplicado para enseñar a un ordenador a mover discos por nosotros o para resolver cuestiones como las que siguen:

  1. Si empezamos con 12 discos, con las notaciones anteriores, ¿qué disco se mueve y a qué torre en el movimiento 1.000?
  2. Si son 20 discos, ¿qué disco se mueve y a qué torre en el movimiento 1.000.000?

CONFIGURACIONES AL AZAR
Ahora los discos están repartidos, al azar, entre las distintas torres, y tendremos que trasladar todos los discos a la torre "DERECHA" para recibir un mensaje de felicitación. Cada vez que cambiemos de número de discos o pulsemos sobre Nueva nos aparecerá, al azar, una nueva configuración.

 

Número de Discos:
Por cierto, ¿cuántas configuraciones distintas hay? Naturalmente, consideramos que dos configuraciones son distintas si al menos un disco se encuentra en torre diferente.

Algunas configuraciones serán muy fáciles de resolver (incluso puede que aparezcan todos los discos en la torre "DERECHA" y seamos felicitados sin haber hecho ni un movimiento), otras no tanto. ¡Qué haya suerte!

Si se tiene especial dificultad con una de las configuraciones se puede ver como se resuelve pulsando sobre el botón.


       
             
  Salvador Calvo-Fernández Pérez
 
© Ministerio de Educación y Ciencia. Año 2001