lunes, 3 de marzo de 2014

Las torres de Hanoi: un puzzle matemático





"En el gran templo de Benarés, debajo de la cúpula que marca el centro del mundo, yace una base de bronce, en donde se encuentran acomodadas tres agujas de diamante, cada una del grueso del cuerpo de una abeja y de una altura de 50 cm aproximadamente. En una de estas agujas, Dios, en el momento de la Creación, colocó sesenta y cuatro discos de oro -el mayor sobre la base de bronce, y el resto de menor tamaño conforme se va ascendiendo-. Día y noche, incesantemente, los sacerdotes del templo se turnan en el trabajo de mover los discos de una aguja a otra de acuerdo con las leyes impuestas e inmutables de Brahma, que requieren que siempre haya algún sacerdote trabajando, que no muevan más de un disco a la vez y que deben colocar cada disco en alguna de las agujas de modo que no cubra a un disco de radio menor. Cuando los sesenta y cuatro discos hayan sido transferidos de la aguja en la que Dios los colocó, en el momento de la Creación, a otra aguja, el templo y los brahmanes se convertirán en polvo y, junto con ellos, el mundo desaparecerá".

Hoy no existe tal templo, pero el juego aún perduró en el tiempo...


Otra leyenda cuenta que Dios al crear el mundo, colocó tres varillas de diamante con 64 discos en la primera. También creó un monasterio con monjes, los cuales tienen la tarea de resolver esta Torre de Hanói divina. El día que estos monjes consigan terminar el juego, el mundo acabará.


No obstante, esta leyenda resultó ser un invento publicitario del creador del juego, el matemático Éduard Lucas. En aquella época, era muy común encontrar matemáticos ganándose la vida de forma itinerante con juegos de su invención, de la misma forma que los juglares hacían con su música. No obstante, la falacia resultó ser tan efectista y tan bonita, que ha perdurado hasta nuestros días. Además, invita a realizarse la pregunta: "si la leyenda fuera cierta, ¿cuándo será el fin del mundo?"

El mínimo número de movimientos que se necesita para resolver este problema es de 2^64-1. Si los monjes hicieran un movimiento por segundo, los 64 discos estarían en la tercera varilla en poco menos de 584942417355,07203247082699137494 años (585 mil millones de años rodeando). Como comparación para ver la magnitud de esta cifra, la Tierra tiene como 5 mil millones de años, y el Universo entre 15 y 20 mil millones de años de antigüedad, sólo una pequeña fracción de esa cifra.

En el mundo existen diferentes tipos de puzzles, algunos más complejos que otros. Entre ellos se encuentran las Torres de Hanoi, las cuales se basan en la matemática y son utilizadas en la psicología.

El juego fue inventado por Edouard Lucas, un matemático que estudió la secuencia de Fibonacci. En la serie creada por Lucas cada número es la suma de los dos anteriores, salvo por los dos primeros ( Por ejemplo: 2 1 3 4 7 11). Junto con esto desarrolló un método para saber cuando los números son primos, el cual todavía es utilizado en el presente.

Cada torre es dividida en torres más pequeñas, que ayudarán a resolver el problema general. Lateoría de la reductibilidad funciona reduciendo los problemas en otros más pequeños, y solucionándolos.


Un poco de historia


En el año 1883, Édouard Lucas d'Amiens (1842-1891) publicó un juego o puzle matemático llamado "La Torre de Hanoi" bajo el pseudónimo deProfesor N. Claus de Siam (nombre que tiene las mismas letras que el suyo auténtico), mandarín del colegio Li-Sou-Stian (el propio Lucas impartía clases en el instituto Saint-Louis). En las ilustraciones de la revista La Nature, donde el escritor francés Henri de Parville lo presentó en 1884, en la sección llamada Récréations Mathématiques, se observan, sobre una superficie rectangular de madera, tres postes verticales, uno de ellos (el de la izquierda) rotulado A y otro (el de la derecha) rotulado B. La ilustración I nos muestra que en el poste A hay insertados ocho discos de madera ordenados de mayor a menor diámetro (de abajo arriba); se trata de la posición inicial del juego. En la ilustración III se ve la posición final: los ocho discos insertados en el poste B, manteniendo el orden indicado. La ilustración II muestra una posición intermedia del desarrollo del puzle. Sólo se puede mover un disco cada vez y no se puede colocar sobre otro de diámetro menor. Estas son las únicas reglas del juego.



 Ilustración de Poyet que acompaña al artículo de De Parville en La Nature



Ignoramos cuándo y cómo pasó a ser llamado "Las Torres de Hanoi", en plural, aunque intuimos la razón: dado que en el desarrollo del juego la torre inicial es distribuida en dos y hasta en tres torres distintas varias veces, es natural que alguien se refiera al juego con el plural. En cambio, parece clara la idea de Lucas: sólo hay una torre, la formada por los discos colocados uno sobre otro al principio y al final del juego. Como quiera que sea, a lo largo de todo este tiempo, el juego se ha difundido por todo el mundo con el nombre escrito en plural.

¿Por qué de Hanoi? En esa época, finales del XIX, Francia formó, a golpe de guerras de invasión colonial, la llamada Indonesia Francesa, que duró hasta 1954 y que incluía los actuales Camboya, Laos y Vietnam. Es de suponer que la prensa francesa se refiriera a estos lugares constantemente, siguiendo el ritmo de las batallas. Hanoi (nombre que significa en chino dentro del río) es la capital de la región del norte de Vietnam, Tonkin. En la portada de la publicación de Lucas puede leerse "Juego traído de Tonkin" y "Verdadero rompecabezas annamita". Annam es la región central de Vietnam, pero es el nombre con el que los chinos, hasta el siglo X dominadores del país, lo llamaban. Los franceses recuperaron este nombre para referirse tanto a la región central como a todo Vietnam, de forma que, en la Francia de finales del XIX, annamita era sinónimo de vietnamita.


Portada original del juego de Lucas, 1883

Viendo la portada del juego, el nombre del supuesto autor y la ilustración (cañas de bambú, personas asiáticas, alguien con frac en primer plano que recuerda a un mono...), se nota un cierto toque de misterio oriental. Ayer, como hoy, todo lo oriental, que esté relacionado con la meditación, tiene su público. Es curioso cómo Lucas va eligiendo y dando los datos, a parte del nombre del autor. Dice que es un juego annamita, traído de Tonkin que se llama Torre de Hanoi. ¿Caben más sitios orientales en menos espacio? Suponemos que una mezcla de interés lúdico e interés comercial conformaron toda la presentación del juego, su nombre y la leyenda que lo acompaña desde su creación.

También este juego ha sido conocido por los nombres de Las torres de Brahma y El problema del fin del mundo. Se deben, sin duda, a la leyenda a la que nos hemos referido. En las instrucciones que acompañaban al juego, Lucas incluyó una referencia a los brahmanes de Benarés (India) y a su templo, no en vano Benarés es considerada la ciudad más antigua del mundo, como afirma Fernando Sánchez Dragó, pero fue un año después, en 1884, cuando De Parville publicó su artículo en la revista La Nature y, en él, desarrolló por completo la leyenda de una forma muy poética. Dice así:

Seguramente, la Torre de Hanoi es de los juegos más conocidos en el mundo matemático. Muchos profesores lo han usado para ilustrar el método de demostración llamado de inducción completa, el concepto de recursividad, conceptos relacionados con la combinatoria, sistemas de numeración... Incluso, como veremos, podría ser usado para mostrar la creación de un fractal.

Es necesario seguir tres simples reglas: 

1. Sólo se puede mover un disco cada vez. 
2. Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo. 
3. Sólo puedes desplazar el disco que se encuentre arriba en cada varilla. 

El juego consiste en pasar todos los discos a la tercera varilla colocados de mayor a menor ascendentemente.

Descubrir la explicación matemática para todos los aspectos posibles del juego, y las relaciones entre ellas:

- número de movimientos totales

- número de movimientos de cada pieza

- secuencia de piezas que se mueven

- apariencia de las torres en un movimiento dado

- número de "tiempos" que espera cada pieza entre cada uno de sus movimientos (es constante)

Demostrar que el juego se basa en potencias de 2.

Al principio puede parecer fácil, pero luego de algunos movimientos nos daremos cuenta de que es más complicado de lo que parece y tiene como fondo principios matemáticos. Los más simples tienen solo 8 discos, y además existen versiones para niños.

Al intentar resolver el puzzle estaremos ejercitando la corteza prefrontal del cerebro, la cual nos ayuda a realizar ejercicios matemáticos, resolver problemas y llevar a cabo discusiones complicadas.

El juego nos ayuda a entender la secuencia de Fibonacci, mediante la cual se explican estos números presentes en todo el universo. A medida que pasamos los discos de un poste al otro, nos damos cuenta de que están presentes las proporciones de la secuencia Fibonacci, mediante la cual un número suma a los dos anteriores en la línea.

La reductibilidad funciona cuando pasamos los discos de un poste al otro, reduciendo el problema y teniendo menos discos para pasar hacia el último. Este principio se utiliza también para la computación, donde los respaldos de información se realizan siguiendo este modelo.

Las torres de Hanoi son reconocidas y han sido utilizadas en varias películas, libros y videojuegos, por ejemplo Doctor Who, Rise of the Planet of the Apes, Mass Effect y Star Wars. Es posible que lo hayamos visto numerosas veces y no nos acordemos, lo cierto es que es un juego interesante para ejercitar nuestras habilidades cognitivas.


Fuente:

http://www.ojocientifico.com
http://olmo.pntic.mec.es
http://www.taringa.net





No hay comentarios:

Publicar un comentario