Inicio > Acertijos > La torre de Hanói
La torre de Hanói es un problema matemático de origen indio que lleva más de un siglo siendo estudiado en matemáticas, informática y psicología cognitiva. Su aparente sencillez esconde una progresión exponencial que sorprende a todo el mundo: mover 64 discos, siguiendo las reglas, requeriría más de 580 mil millones de años.
Aquí encontrarás la solución completa, la recurrencia matemática y la fórmula cerrada para cualquier número de discos.
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?
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, lo que exige otros $T(n-1)$ movimientos.
Por tanto:
$$ T(n)=T(n-1)+1+T(n-1)=2T(n-1)+1. $$
Como $T(1)=1$, se obtiene:
$$ T(n)=2^n-1. $$
Para 7 discos:
$$ T(7)=2^7-1=128-1=127. $$
Así que el mínimo es 127 movimientos.
Si te gustó este reto, prueba más acertijos de lógica pura, explora esta temática, revisa el archivo completo o mira la guía para resolver acertijos.