martes, 22 de enero de 2008

Torre de Brahma - I

Es Leyenda

Dicen que en la India, en un lugar secreto de la ciudad de Benares, oculto bajo la tierra, hay un templo que está precisamente localizado en el centro del mundo. Allí, desde el principio de los tiempos, aún antes que se dieran a conocer los relatos védicos, hay un grupo de devotos que guardan su existencia y sus rituales en el más profundo secreto.

A este templo solamente llegan aquellos devotos que han demostrado un profundo compromiso y son dueños de una fe inquebrantable y una precisión absoluta en sus movimientos. Todo lo que harán por el resto de sus vidas, es participar en el traslado de la Torre de Brama. La torre consiste de tres varas dispuestas en paralelo y representan los tres modos o polaridades de la energía.

En el principio, en una de las varas, estaban colocados 64 discos de oro, dispuestos de menor a mayor, y la misión de los monjes es la de trasladar estos discos hasta la tercer varilla, la varilla correspondiente al neutro o el perfecto equilibrio de los dos polos opuestos. Al hacer esto, deben mantener siempre los discos mas pequeños encima de los grandes. Este dispositivo es un reloj cósmico que marca el tiempo del mundo, porque al terminar de pasar todos los discos de oro, el mundo entero se disolverá.

Fig. 1 El juego de La Torre de Hanoi

Es Matemáticamente Posible


El matemático Edouard Lucas creó esta leyenda romántica para presentar un juego: La Torre de Hanoi. Lucas trabajó mucho en la teoría del número y estudió las series de Fibonacci, incluso desarrolló sus propias series: Las Series de Lucas. Lo que La Torre de Hanoi y la leyenda nos enseña, es que con un número pequeño de objetos, se puede generar un número extraordinariamente grande de movimientos.

En el caso de las “torres”, 2 ^ N – 1, es decir, si contamos con 3 discos:

2 ^ 3 – 1 = 7 movimientos.

En el caso de la torre de 64 discos:

2 ^ 64 – 1 = 18.446.744.073.709.551.615 movimientos.

Si los monjes realizaran un traslado completo de disco en 1 segundo, para desplazar los 64 discos, tardarían casi: ¡600 Billones de años!

Es Educativo Hacerlo en Excel

El algoritmo de las torres me resultó siempre interesante por su simpleza y por las implicancias que tiene. En una ocasión, lo implementé en un microprocesador 6800 donde tuve que ensamblar en el papel el código de máquina y luego cargarlo en la memoria con un teclado hexadecimal. ¿Un algoritmo recursivo en lenguaje de máquina? Por supuesto que sí. Tal vez haga una versión en lenguaje ensamblador 8086 y lo publique aquí en el futuro.

Para los alumnos, la implementación del algoritmo de Las Torres de Hanoi es interesante como ejercicio práctico del uso de los recursos de Excel. Es una forma de hacer que los gráficos interactúen con los programas de Visual Basic, además de tener que "animar" la secuencia de desplazamientos por lo que hay que considerar el manejo del tiempo.

Fig. 2 Implementación de “Las Torres de Hanoi” en Excel

En entregas futuras vamos a explorar el proceso de implementación de este algorítmo.

Que tengan un gran día!

Sergio Otaño

1 comentarios:

Sergio Otaño dijo...

Recientemente el artículo junto con los ejemplos en Excel fue publicado en un sitio dedicado a los algorítmos de las torres de hanoi:
http://hanoitower.mkolar.org/THnewURL.html