27/08/2010

DOBLE CIEGO : El fin del mundo

---

Se cuenta que allá por 1883, Édouard Lucas inventó un juego matemático al que llamó "Torres de Hanoi". Consciente de lo importante que es la publicidad, decidió inventar una leyenda india que justificara la existencia del juego, y que hiciera creer que este era muy antiguo.

La leyenda cuenta que en la India existia, en la ciudad de Benarés, un domo que marcaba el centro del mundo, bajo el que se ubicaba una placa de latón, con tres agujas de diamante. Durante la creación del mundo, Brahma habría colocado 64 discos de oro puro, ordenados en diámetro descendente, sobre una de las agujas. Luego creó una determinada cantidad de monjes para que cuidaran de este templo, a quienes ordenó que se dedicaran a mover la columna de discos de la aguja en la que el la colocó a otra de las dos restantes, respetando las siguientes 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.

Según el dictado Brahmánico, el día en que los monjes concluyan su tarea el mundo encontrará su fin.



Dejando la leyenda de lado, el juego resulta muy interesante. La cantidad de movimientos que deben hacerse para solucionar el problema en forma óptima (N) crece exponencialmente con el número de discos (n). Más específicamente, es N=2^n-1, lo que puede mostrarse por inducción sobre el número de discos. Como dice la wiki: para el caso de la leyenda, suponiendo que se mueve un disco por segundo, tomaría a los monjes unos 585000 millones de años terminar la tarea... Y si los monjes fueran municipales, esto demostraría más allá de toda duda la eternidad del universo.

La otra cosa interesante es que este problema parece ser un clásico en la introducción a los algoritmos recursivos. Basicamente la idea de la recursividad es como "empezar por el final del juego". Si suponemos que ya movimos todos los discos en el orden correspondiente al poste que queremos, excepto el de menor diámetro, que quedo en alguno de los otros dos, entonces la solución es muy simple: Movemos el disquito y lo ponemos sobre la torre, y juego terminado. Eso es equivalente a resolver el juego para un único disco.
Entonces, el problema puede plantearse de esta manera: Resuelvo el juego para los (n-1) discos mas chicos, moviéndolos a uno de los dos postes. Después resuelvo el juego para 1 disco (el más grande), moviéndolo al otro poste. Por último, resuelvo de nuevo el juego para (n-1) discos, moviéndolos sobre el disco mayor.
¿Y como se resuelve el problema de (n-1) discos? Exactamente igual, primero para (n-2), luego para 1, luego para (n-2) otra vez... y así, hasta un disco.

Dejo acá el algoritmo escrito en C. Parece mentira, pero funciona, jej.