Reto #3: Las Torres de Hanói.

Contexto

La Torre de Hanói 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.

Ejemplo de cómo jugar las torres de Hanói:

¿Qué hay que hacer?

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

-Analice los resultados solicitados en el párrafo anterior 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.

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

Entonces tenemos:

1.   Número de movimientos necesarios para mover los discos de una torre hacia otra torre teniendo:

1 Disco: 1 movimiento

            2 Discos: 3 movimientos

            3 Discos: 7 movimientos

2.    Obteniendo fórmula recursiva:

# de Discos	Cantidad de movimientos mínimos
1	a1=1
2	a2=3
3	a3=7
4	a4=15
5	a5=31
n	Fórmula recursiva: an=2an-1+1

Obtener número de movimientos necesarios utilizando 4 discos:

a_n=2a_n-1+1

a₄=2(7)+1

a₄=14+1

a₄=15

Se necesitan mover 15 veces los discos cuando se tienen 4 discos.

3.    Obteniendo fórmula explícita:

Tenemos:

            Análisis hacia adelante:

a₁=1

a₂=3   =  2a₁+1   = (2*1)+1

a₃=7   =  2a₂+1   = 2(2*1+1)+1         =2²*1+2+1

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

a₅=31  = 2a₄+1   =2(2³*1+2²+2+1)+1    =2⁴*1+2³+2²+2+1

a_n=2^n-1+2^n-2+2^n-3+…+2³+2²+2¹+1

Con la fórmula: 1+2+2²+…+2ⁿ=2ⁿ⁺¹-1, se obtiene la fórmula explícita: a_n=2ⁿ-1

Ahora ya resuelto el reto nos gustaría que vieran desde otra perspectiva el juego de las torres de Hanoi, ahora basándose en un programa de un robot que conociendo la fórmula para determinar la secuencia del juego, puede aplicarla para resolver el problema...

Para completar conocimientos también pueden jugar el Juego de las Torres de Hanoi.

 

Esperamos que hayan disfrutado de todos los materiales que brinda el blog, así como nuevas experiencias y conocimientos. Finalmente, nada más agregar las respectivas referencias bibliográficas que fueron de gran ayuda para el blog:

Referencias bibliográficas

 

1. Aplicación de la serie de Fibonacci. Recuperado el 29 de mayo de 2011 de, http://mercado-continuo.blogspot.com/2006/08/aplicacin-de-la-serie-de-fibonacci.html

2. Sucesión de Fibonacci. Recuperado el 31 de mayo de 2011, de http://es.wikipedia.org/wiki/Sucesi%C3%B3n_de_Fibonacci

3.    Fractal. Recuperado el 02 de junio de 2011, de http://es.wikipedia.org/wiki/Fractal

4. Secuencia de Fibonacci y Divina Proporción, matemáticas que rigen la vida. Recuperado el 02 de junio de 2011, de http://sobrecuriosidades.com/2009/05/07/secuencia-de-fibonacci-y-divina-proporcion-matematicas-que-rigen-la-vida/