viernes, 22 de abril de 2011

Las Tores de Hanoi y el Fin del Mundo


Si le preguntáis a un informático si conoce el problema de Las Torres de Hanoi casi con toda seguridad os responderá afirmativamente, ya que se trata de uno de los problemas más conocidos en el mundo de la programación, y es que es usado a menudo para explicar la recursividad. Pero fuera de este ámbito es mucho menos conocido.
Imaginad que tenemos tres varas verticales, y en una de ellas apilamos un número indeterminado de discos de forma que su diámetro es más decreciente cuanto más alto esté, y las otras dos varillas están vacías. El juego consiste en pasar todos los discos de la varilla ocupada a cualquiera de las otras, pero siguiendo 3 simples reglas:
1. Sólo se puede coger un disco en cada movimiento
2. Un disco no puede descansar sobre otro más pequeño
3. Sólo se pueden coger los discos que estén en la cima de las 3 varillas

Existen diversas formas de realizar la solución final, pero nos encontramos con que aunque éstas son fáciles de calcular el número de pasos para resolver el problema, en el mejor de los casos, crece exponencialmente conforme aumenta el número de discos a mover*.


Entre las leyendas sobre el fin del mundo se encuentra una centrada en el problema de las torres de Hanoi. En el gran templo de Benarés, bajo la cúpula que señala el centro del Mundo reposa una bandeja de cobre en la que están plantadas tres agujas de diámetro más fino que el aguijón de una abeja. En el momento de la Creación, Dios colocó en una de las agujas 64 discos de oro puro ordenados por tamaño: desde el mayor que rebosa sobre la bandeja hasta el más pequeño, en lo más alto del montón. Es la torre de Brahma. Incansablemente, día tras día, los sacerdotes del templo mueven los discos haciéndoles pasar de una aguja a otra, de acuerdo con las leyes fijas e inmutables de Brahma. El día en que los 64 discos hayan sido trasladados desde la aguja en que Dios los puso al crear el mundo a una cualquiera de las otras dos agujas, ese día la Torre, el Templo y, el Mundo desaparecerán.

Teniendo en cuenta que el mínimo número de movimientos que se necesita para resolver este problema es de 264-1, si la leyenda fuera cierta y los monjes hicieran un movimiento por segundo (no un día como dicta la leyenda), los 64 discos estarían en la tercera varilla en algo menos de 585 mil millones de años.



Referencias:
1. http://es.wikipedia.org/wiki/Torres_de_Han%C3%B3i

* Por ejemplo, para sólo 4 discos habría que hacer 15 movimientos, siempre que no fallemos en alguno de ellos; y para 6 discos pasamos a 65.

0 comentarios:

Publicar un comentario