Inicio > Acertijos > La torre de Hanói (tradición india)
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 $n$ discos de distintos tamaños, apilados de mayor a menor. Solo puedes mover un disco cada vez y nunca poner uno grande sobre uno pequeño.
¿Cuál es el número mínimo de movimientos necesarios para trasladar toda la torre a otra varilla?
Problema clásico atribuido al rompecabezas de Brahma
Respuesta: El mínimo es
$$ T(n)=2^n-1. $$
Explicación:
Para mover $n$ discos:
Eso da la recurrencia:
$$ T(n)=T(n-1)+1+T(n-1)=2T(n-1)+1,\quad T(1)=1. $$
Resolviendo:
$$ T(1)=1,\;T(2)=3,\;T(3)=7,\ldots \Rightarrow T(n)=2^n-1. $$
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.