Las torres de Hanoi

La Torre de Hanoi es un juego que consiste en tres estacas montadas en una tabla y n discos de varios tamaños con agujeros en sus centros. Se supone que si un disco está en una estaca, sólo un disco de diámetro más pequeño se puede colocar encima de él. Si se tienen todos los discos apilados en una estaca específica inicial, el problema consiste transferir los discos a otra estaca moviendo un disco a la vez.

Sobre el juego de las Torres de Hanoi, realice lo siguiente:
1.Calcule, para cada caso, el número de movimientos necesarios para mover los discos de la torre donde se encuentren inicialmente hacia otra torre, tomando en cuenta que el juego posea 1 disco, 2 discos y 3 discos (cada caso por separado).
2. Analice los resultados del punto (1) e induzca una fórmula recursiva que le permita calcular el número de movimientos requeridos. Con esta fórmula, infiera el número de movimientos mínimos que necesitaría realizar una persona, sabiendo que el juego de las Torres de Hanoi dispone de 4 discos.
3. Induzca una fórmula explícita que le permita calcular, a partir del número de discos “n”, el número de movimientos mínimos requeridos para resolver el juego de las Torres de Hanoi.

1. Calcular cantidad de movimientos para:

1 disco  = 1 movimiento

2 discos = 3 movimientos

3 discos = 7 movimientos

2. Se puede inducir que la fórmula recursiva para esta sucesión es:

Por lo que para 4 discos se necesitarían 15 movimientos.

3. La fórmula explícita de la sucesión:

(la demostración de esta fórmula se encuentra en el reto La buena paga)