La torre de Hanói (tradición india)

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*

1. Para mover n discos: Mueves los n-1 superiores a una varilla auxiliar.
2. Para mover n discos: Mueves el disco mayor (1 movimiento).
3. Eso da la recurrencia: T(n)=T(n-1)+1+T(n-1)=2T(n-1)+1, T(1)=1.

**Respuesta:** El mínimo es
$$
T(n)=2^n-1.
$$

{ width=700px align=center }

**Explicación:**

Para mover $n$ discos:

1. Mueves los $n-1$ superiores a una varilla auxiliar.
2. Mueves el disco mayor (1 movimiento).
3. Mueves de nuevo esos $n-1$ discos sobre el mayor.

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.
$$

---