Pocas piezas unen tan bien mecanismo y crecimiento. Cada movimiento es sencillo; lo asombroso aparece cuando esa simplicidad se repite hasta producir una cantidad inesperadamente grande.
La torre de Hanói
Enunciado
Hay tres varillas y una torre de 7 discos de distintos tamaños, apilados de mayor a menor en una de ellas.
Solo puedes mover un disco cada vez y nunca puedes colocar un disco grande sobre uno pequeño.
¿Cuál es el número mínimo de movimientos necesario para trasladar toda la torre a otra varilla?
Ver solución
Solución
Respuesta: hacen falta 127 movimientos.
Para mover una torre de $n$ discos, el disco mayor no puede moverse hasta que los $n-1$ discos superiores estén en la varilla auxiliar. Ese primer bloque exige $T(n-1)$ movimientos.
Después se mueve el disco mayor una sola vez.
Por último, hay que trasladar los $n-1$ discos desde la varilla auxiliar hasta la varilla de destino: otros $T(n-1)$ movimientos.
La recurrencia resultante es:
Con la condición inicial $T(1) = 1$, se obtiene la fórmula cerrada:
Para $n = 7$:
El mínimo es 127 movimientos.