El origen del planeta de los simios: Las torres…¿de Lucas? ¿o de Hanoi?

Por ocurrir al principio de la película, no es ningún spoiler decir que una de las primeras sorpresas que se encuentran los científicos que experimentan con chimpancés es ver cómo uno de ellos es capaz de resolver un puzle o juego, al que en la película llaman «torres de Lucas«:

Secuencia donde aparecen las torres de Hanoi (Copyright: 20th Century Fox)

Lo cierto es que el juego lo inventó en 1883 por el francés Édouard Lucas, por lo que el nombre está justificado, pero todo el mundo ha usado siempre otro nombre para referirse a ese juego: Las torres de Hanoi. 

¿Por qué le han cambiado el nombre en la película? No he encontrado ninguna respuesta lógica, por lo que pienso que quizás «Torres de Hanoi» sea una marca registrada en algún país y han querido curarse en salud.


El juego se trata de un problema de lógica, archifamoso entre estudiantes de ciencias de la computación (antiguos planes de ingeniería en Informática en España) por tener una solución que es un excelente ejemplo de recursividad.




¿En qué consiste?

Para los que no lo conozcan, se trata de un juego con tres palos donde empezamos siempre con una serie de discos de distintos tamaños colocados en el primero en orden decreciente de tamaño. El objetivo es trasladarlos todos hasta el tercer palo, siguiendo siempre estas dos reglas: (1) sólo se puede mover un disco a la vez, (2) un disco sólo puede apoyarse en uno de tamaño mayor.

Torres de Hanoi con ocho discos (Créditos)

En cuanto se piensa un rato sobre cómo resolverlo, se llega a la conclusión de que existe una forma recursiva de resolverlo:

1. Movemos los N-1 primeros discos del palo 1 al palo 2.
2. Mover el último disco N desde 1 al 3.
3. Mover los N-1 que teníamos en 2 hasta el 3, para lo que hay que repetir recursivamente desde el punto 1, pero cambiando la numeración de los palos.

El número mínimo de movimientos necesarios para resolver unas Torres de Hanoi con N discos es de 2^N-1. Podéis contar cómo en el siguiente ejemplo con N=4 se termina tras 2^4-1=15 movimientos. Como pasos intermedios, se consiguen colocar los 3 primeros discos en el palo central tras 2^3-1=7 movimientos, o los 2 primeras discos en el último palo tras 2^2-1=3:

Animación de la solución para cuatro discos (Créditos)

Para los amantes de la programación, existen webs que proporcionan soluciones recursivas usando pilas (stacks) para C++ o esta otra en Python.

La (falsa) leyenda Hindú