martes

1: Las Torres de Hanoi.

No hace mucho que ha pasado el 21 de diciembre de 2012, así que aún me chirría en los tímpanos eso de que los mayas habían profetizado para tal fecha el fin del mundo, cuando lo único que habían reseñado para la ocasión era el comienzo de un nuevo ciclo astronómico. Bien calculado, por cierto.
Pero hoy no vamos a territorio maya. Hoy, aunque Hanoi sea una ciudad vietnamita, nos vamos a la India y a Francia.

En Benarés sí que existe una profecía sobre el fin del mundo. En el Templo de Brahma, bajo la cúpula principal, existen tres varillas verticales (hay quien dice que las originales eran de diamante, que queda muy bonito…) clavadas sobre un soporte de madera. Lo habitual es designarlas, de izquierda a derecha, A, B, C. Cuando un monje le preguntó a Brahma durante cuánto tiempo iba a existir el universo, Brahma contestó ensartando en la primera varilla sesenta y cuatro discos de oro por orden de tamaño, siendo el situado en la base el disco de mayor diámetro y el que ocupa la posición más alta el más pequeño.
Brahma dio a los monjes las siguientes instrucciones:
1/ Mover un disco consiste en sacarlo de una varilla y ponerlo en otra.
2/ Sólo podéis mover un disco cada día.
3/ Jamás puede ponerse un disco encima de otro que tenga menor diámetro.
4/ Cuando los 64 discos, ordenados de mayor a menor, estén en la tercera varilla, la cúpula, el templo y el mundo entero desaparecerán.
Esto sí que es una profecía, aunque no tenga fecha explícita.
Para un espíritu matemático, la fecha está implícita en las instrucciones y, por supuesto, la tentación de calcularla es irresistible.
Empecemos por simplificar el problema: ¿cuántos movimientos puedo hacer si el número de discos es cero? Respuesta obvia: ninguno. Ya tenemos una primera pareja de valores: a cero discos corresponden cero movimientos.
Sigamos. ¿Cuántos movimientos puedo hacer con un disco? Poder, lo que se dice poder, puedo hacer infinitos movimientos entre la varilla A y la varilla B, dado que las instrucciones no prohiben deshacer movimientos ya hechos. Pero esa respuesta es muy mala. ¿Por qué? Porque la pregunta era peor aún. Hagamos la pregunta correcta: ¿cuántos movimientos son necesarios y suficientes para alcanzar el objetivo? Muy sencillo: quitamos el disco de la varilla A y lo ponemos en la C: un movimiento.
¿Y si tenemos dos discos? ¿Y si tenemos tres, cuatro...?




La respuesta puede verse en los diagramas adjuntos, que nos llevan a la conclusión (habría que demostrarla para n+1, ya sé, lo pasamos por alto...) de que el número mínimo de movimientos necesarios para completar la tarea es mov=2n - 1
Lo que, aplicado al caso n=64 nos arroja la cifra de 18.446.744.073.709.551.615.

Dicho de otro modo, si los monjes no cometen ningún error (hecho un movimiento, tienen todo el día para pensarse el siguiente...), la profecía se cumplirá dentro de, lo voy a escribir en notación científica, 5'054.1016 años.

No hay motivo para alarmarse. Da tiempo a que el Sol consuma todo el hidrógeno disponible, empiece a fusionar helio, se transforme en una gigante roja, evapore a Mercurio, a Venus, a la Tierra junto con la Luna y puede que también a Marte, acabe el helio, se enfríe, se apague y muera.

No hacía falta que Brahma tomase tantas precauciones, eligiendo el número 64. Con la mitad de discos, con 32, bastaba y sobraba. Con 32 discos, la tarea requiere 11767 milenios. Muchísimo más de lo que razonablemente durará la humanidad.

Espera. No hemos dicho ni media palabra de cómo se resuelven las torres de Hanoi, cómo se pasan todos los discos ordenados a la varilla C.

Ni hemos dicho nada de Francia. Esto se arregla rápido: Edouard Lucas, un matemático francés, dijo en 1883 que el juego era invento suyo y lo patentó en su versión de 8 discos, incluyendo la leyenda anterior a modo de introducción para las instrucciones.

Hay quien sostiene que el Templo, las agujas, los 64 discos, existieron realmente en alguno de los miles de templos de Benarés; los monjes, alejados de miradas indiscritas, prosiguen hoy día, quizá, su callada labor.
Y hay quien sostiene que la leyenda es una patraña publicitaria inventada por Edouard Lucas, que solía autoplocamarse "profesor de Siam", para darle al juego un toque exótico y aumentar las ventas.
Sea como sea, si alguien quiere investigar cuál de las dos versiones es la cierta, hasta que se cumpla la profecía tiene tiempo de sobra.

¿Y cómo se resuelve? No perdiendo la paridad del conjunto de discos. Numerando de abajo a arriba, los discos son 1,2,3,4,5,...,n. O sea, impar, par, impar, par, impar, par,...,n.
Si n es par, el primer movimiento debe ser de la varilla A a la varilla C.
Si n es impar, el primer movimiento debe ser de la varilla A a la varilla B.
A partir de ahí, basta con no alterar la paridad del sistema. Dicho en lenguaje coloquial: no pongas nunca un disco par sobre otro par ni un disco impar sobre otro impar y acabarás el puzzle; si en algún momento te es imposible respetar esta regla, es que ya te has equivocado antes.

Como la clave está en no perder de vista qué discos ocupaban inicialmente posición par y qué discos ocupaban inicialmente posición impar, es más fácil resolver este juego


que este otro



En internet hay cientos de simuladores de las torres de Hanoi.
¿Por qué no pruebas?

No hay comentarios:

Publicar un comentario

Contador

Flag Counter