Las torres de Hanoi

La Torre de Hanoi es un juego que consiste en tres estacas montadas en una tabla y n dis­cos 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 enci­ma 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.

Número de Discos

1

2

3

4

5

:

N

Cantidad de Movimientos

a1=1 a2 = 3 a3 = 7 a4 = 15 a5=31 : an =2n-l 1
a2 = 3	= ai+1	= (2*1) + 1
a3 = 7	= a2+l	= 2(2*1 + 1) + 1
a4 = 15	= a3+l	= 2(22*l + 2 + l) + l
a5 = 31	= a4+l	= 2(23*l + 22 + 2 + l)

a_n = 2a„.i+l a_n= 2""¹ + 2"^ + ... + 2^¿ + 2²+ 1

-Usando la fórmula: 1 + 2+2²+... +2ⁿ = 2ⁿ*¹-l podemos obtener como resultado a_n= 2ⁿ-l para conocer el minimo de movimentos necesarios para ndiscos.

El mínimo de movimientos necesarios para mover una cantidad de 4 discos

serían:

a₄ = 2ⁿ-l

= 2⁴-l

= 16-1

= .'. 15 es el total de movimientos mínimo para un juego con 4 discos