El Juego De La Torre De Hanoi

El juego de la Torre de Hanoi fue publicado por el matemático francés Edouard Lucas en 1883. Este consiste de tres barras verticales y $n$ discos agujerados de tamaños diferentes (dos a dos) que son colocados en orden decreciente uno sobre el otro en una de las barras. El objetivo del juego es transferir toda la pila de discos a otra barra moviendo los discos uno por uno (uno por vez) sobre las barras con la única condición de no colocar un disco de tamaño mayor sobe un disco de tamaño menor. Muestra que es posible resolver este juego en $2^n-1$ movimientos.

Haciendo inducción sobre el numero de piezas $n$.

La proposición es claramente valida si $n=1$ sólo se necesita un movimiento $1=2^1-1$, suponiéndolo verdadero para $n-1$ (mover $n-1$ piezas requiere $2^{n-1}-1$ movimientos). Por Demostrar que mover $n$ piezas requiere $2^n-1$ movimientos.

En efecto, si se empieza con todas las piezas en la barra $A$, para poder mover la pieza de hasta abajo primero se tiene que mover las $n-1$ piezas de arriba a la barra $B$ esto por hipótesis inductiva requiere $2^{n-1}-1$ movimientos. Después, mover la última pieza a la barra $C$ toma un movimiento y, por último, pasar las $n-1$ piezas de la barra $B$ a la $C$ otros $2^{n-1}-1$ movimientos quedando un total de $[2^{n-1}-1]+1+[2^{n-1}-1]=2*2^{n-1}-1=2^n-1$ movimientos lo que completa la prueba.

Si no se indica lo contrario, el contenido de esta página se ofrece bajo Creative Commons Attribution-ShareAlike 3.0 License