La torre de Hanoi

Este problema se debe al matemático francés Edouard Lucas (1843-1891), quien le atribuyó un origen oriental.

Para alcanzar la solución conviene empezar con un caso más sencillo. Supongamos que sólo tenemos un disco en el eje A, para pasarlo al C, necesitamos un solo movimiento.

Si los discos son dos, es un poco más complicado. Tendremos que llevar el disco superior al eje auxiliar B (1), luego llevaremos el otro disco a C (2) y por fin el disco pequeño lo movemos también a C (3).

Conviene notar que lo que hemos hecho es utilizar el eje B como si hubiera sido el C en el caso anterior de un solo disco, para luego llevar el segundo y último disco a C y ahora pasar el disco pequeño también a C.

En el caso de tres discos, el proceso es similar. Primero, utilizamos C como auxiliar, para colocar los dos primeros discos (rojo y verde en el dibujo) en B (1, 2 y 3). Luego llevamos el tercer disco (amarillo) a C (4) y después utilizamos el eje A como auxiliar para llevar el verde y el rojo también al C (5, 6 y 7).

Es decir, sea cual sea el número de discos el proceso es iterativo. Si hemos de traspasar "n" discos A al C, primero tendremos que colocar "n-1" en B, lo cual implica haber colocado "n-2" en C, etc.

Por tanto, los movimientos necesarios para colocar los discos son: .

1 disco : 1 movimientos (1 = 2 - 1 = 2^1 -1)

2 discos: 3 movimientos (3 = 4 - 1 = 2^2 -1)

3 discos: 7 movimientos (7 = 8 - 1 = 2^3 -1)

y así sucesivamente.

En general, para mover "n" discos de A a C son necesarios un total de 2^n - 1 (2 elevado a "n", menos 1) movimientos. Esta fórmula se puede demostrar fácilmente por inducción matemática si se tiene en cuenta que para colocar "n+1" discos es necesario colocar primero "n" discos en B, pasar el último disco a C y colocar "n" discos en C. Esto es, para "n+1" discos se necesitan el doble de movimientos que para "n", más 1.

Por tanto, para colocar cinco discos, harán harán falta 31 movimientos (2^5 -1), sin más que seguir el proceso iterativo.

Según Edouard Lucas, una leyenda afirma que en un templo de Benarés hay tres ejes, en el primero de los cuales, Dios, al crear el mundo, puso 64 discos. Desde siempre, incontables generaciones de brahmanes realizan las operaciones necesarias para pasar todos los discos al tercer eje, siguiendo las reglas ya indicadas. Cuando terminen de hacerlo, se acabará el mundo. Suponiendo que los brahmanes inviertan sólo un segundo en el proceso de cambiar un disco de un eje a otro (porque ya tienen mucha práctica), ¿serías capaz de calcular cuánto tiempo tardarían en cambiarlos todos?¿podemos estar tranquilos?.