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. |
|||||||||||||||||
|
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:
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:
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". | |
|
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:
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:
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. 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:
|
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. | |
|
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! |
Salvador Calvo-Fernández Pérez | ||
Ministerio de Educación, Cultura y Deporte. Deporte. Año 2001 | ||
Los contenidos de esta unidad didáctica están bajo una licencia de Creative Commons si no se indica lo contrario.