#3 La 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	Cantidad de movimiento	¿Cómo calculamos la cantidad de movimientos?
1	1	a1=  1
2	3	a2= 2 a1 + 1
3	7	a3= 2 (2 a1 + 1)+1

Entonces la columna tres nos muestra que sucede cada vez que se aumenta un número, con estas pistas logramos calcular la formula recursiva que aparece a continuación:

an= 2 an-1 + 1

 

Entonces con la formula anterior vamos a calcular lo que sucede si tuviéramos cuatro discos.

Tenemos:

a_n= 2 a_n-1 + 1

a₁=  1

a₂= 2 ×1 + 1

a₃= 2 (2 + 1) +1

a₄= 2 (2²+2 + 1) +1 = 2³+2² + 2+1=15

a_n= 2^n-1+2^n-2+…….+2²+2+1

Entonces asuma que:

1+2+2²+2³………+2ⁿ= 2ⁿ⁺¹ – 1

Asumiendo lo anterior podemos  realizar la formula explícita para calcular el número de movimientos de las Torres de Hanoi:

a_n=2^(n-1)+1 – 1

a_n=2ⁿ – 1……………….. Fórmula Explícita

SI desean realizar el experimento en este link encontrarán un juego de las torres de Hanoi: http://juegos.todoenlaces.com/online/871/Las_Torres_de_Hanoi.html