Torre de Hanoi
Fue presentado en 1883 por el matemático francés Edouard Lucas (1842 - 1891).
El problema consistía en lo siguiente: hay que mover una torre, compuesta de discos de diferentes tamaños, de una aguja a otra. Sólo hay dos reglas:
- Sólo se puede mover un disco a la vez
- No está permitido mover un disco encima de otro más pequeño
Según Lucas el juego había sido rescatado por el Profesor N. Claus de Siam. La leyenda contaba que en el templo de Benarés, Dios colocó durante la creación 64 anillos en una aguja. Desde entonces los bramanes, durante incontables generaciones, han estado moviendo los discos de acuerdo con las reglas de arriba. Cuando hayan conseguido mover todos los discos, el templo se derrumbará y el mundo se desvanecerá.
Sin embargo la leyenda fue inventada (N. Claus de Siam es un anagrama de Lucas d'Amiens) para hacer el juego más atractivo.
La torre de Lucas tenía 64 discos. Suponiendo que podemos realizar un movimiento por segundo (bastante realista), ¿Cuánto tiempo tardaremos?
La solución
Para resolver esto, empezamos por supuesto con algo más fácil y lo más fácil que hay es una torre compuesta por un único anillo. ¿Cuántos movimientos necesitamos? Evidentemente uno solo.
¿Y con dos discos? En este caso necesitamos 3 movimientos.
¿Y con 3 discos? (Venga, éste es el último)
Ahora probamos con n discos. Simplemente reducimos este problema a otro ya resuelto (el de n-1 discos). Necesitamos y(n-1) movimientos para mover los n-1 discos superiores a otra aguja, 1 para mover la base y otros y(n-1) para volver a mover los 3 discos y ponerlos encima de la base.
Generalizando: y(n) = 2 × y(n-1) + 1
Bien, por lo menos es algo. Ahora podemos calcular el número de movimientos de forma recursiva. Por otro lado, podemos llegar a una expresión que nos permita calcular de forma directa el número de movimientos para y(n). Tan sólo hay que realizar algunas operaciones básicas:
y(n) = 2 × y(n-1) + 1
y(n) + 1 = 2 × y(n-1) + 2
definimos w(n) = y(n) + 1
concluimos: w(n) = 2 × w(n-1) = 2 × 2 × w(n-2) = ... = 2n
resubstitución: y(n) = w(n) - 1 = 2n - 1
El resultado
La torre de Lucas tenía 64 discos y necesitábamos 1 segundo por movimiento. Con la fórmula de arriba: 264 - 1 segundos = 1,844*1019 segundos que son unos = 0.5849 × 1012 años. ¡Mucho más que la edad del Universo! Para un estudio más completo, una buena página es la de Rodolfo Valeiras.
