Torres de Hanoi: un ejemplo de juego reglado

Las Torres de Hanoi es un acertijo matemático que consiste de tres postes y varios discos de diferente diámetro con un orificio central, de manera que se puedan ensartar en los postes. Es un juego reglado --muy útil para adquirir la disciplina de jugar de acuerdo a unas reglas... y para otras proficiencias en el problem solving.

Foto por Evanherk (Wikipedia)

Estados y movidas

En el estado inicial del juego, todos los discos están en el poste 1 formando una pila, de tal manera que cada uno de ellos descansa sobre uno de mayor diámetro. En otras palabras, están en orden ascendente de tamaño --el superior es el de diámetro mínimo y el inferior es el de diámetro máximo.

El estado meta es esa misma pila en el poste 3 con los discos en el mismo orden del estado inicial.

Las movidas o jugadas legales para lograr ese estado meta o final están sujetas a las siguientes reglas:

• Inicialmente se mueve el disco superior del poste 1 a cualquiera de los otros postes;
• cada una de las movidas posteriores consiste en trasladar el disco superior (de alguna de las pilas que se han formado) a otro poste;
• está prohibido colocar un disco sobre otro de menor diámetro. 

En resumen: mover un disco a la vez y nunca colocar un disco sobre otro de menor tamaño.

Nota: se suele agregar la restricción de que el estado meta se logre con el mínimo número de movidas. Ver http://en.wikipedia.org/wiki/Tower_of_Hanoi para más detalles.

Sitios web con interactivos de las Torres de Hanoi

http://www.mazeworks.com/hanoi/index.htm

http://www.cut-the-knot.org/recurrence/hanoi.shtml

http://thinks.com/java/hanoi/hanoi.htm

http://www.mathsisfun.com/games/towerofhanoi.html

http://www.cosc.canterbury.ac.nz/mukundan/dsal/ToHdb.html (animación)

http://math.bu.edu/DYSYS/applets/hanoi.html

http://thinks.com/java/hanoi/hanoi.htm

Comentarios sobre la solución

El juego de las torres de hanoi es un ejemplo del método de resolución de problemas basado en casos particulares con números pequeños... Y después generalizar usando inducción.

Pero también es útil como ejemplo prototipo de problemas de estados y movidas: a partir un estado inicial, se quiere llegar a uno final, o estado meta, usando movidas legales (que se apegan a ciertas restricciones).

Para un disco se necesita una sola movida, para dos se necesitan 3, para tres... bueno para tres ya está más difícil... Pero podemos usar la solución  que ya sabemos para dos discos: traslado primero los dos superiores al poste intermedio (tres movidas), luego paso el disco inferior al poste 3 (una movida) y, finalmente, los dos del poste intermedio los paso al poste 3 (tres movidas). En total son 3+1+3=7.

De la misma manera puedo obtener el número de movidas para trasladar 4 discos al poste 3: 1) traslado los 3 superiores al poste intermedio (7 movidas), 2) paso el disco inferior al poste 3 (una movida) y, finalmente, paso los 3 discos del poste intermedio al poste 3 (7 movidas). En total son 7+1+7=15 movidas.

El procedimiento es fácilmente generalizable a n discos. Pero no solamente es generalizable para calcular el número de movidas, sino también para el procedimiento de trasladar los discos del poste uno al 3. Es decir, si lo sabes para dos lo sabes para 3, y si lo sabes para 3 lo sabes para 4, etc.

Solución para 2 discos

Inicialmente hay dos discos en el poste 1. Quiero pasarlos al poste 3 de acuerdo a las reglas. Entonces paso el disco pequeño del poste 1 al poste 2 (una movida), paso el disco grande del poste 1 al poste 3 y, finalmente, paso el disco pequeño del poste 2 al poste 3. Llamemos a este procedimiento $P_2$.

Solución para 3 discos

• Aplico $P_2$ para pasar los dos discos superiores en el poste 1 al poste 2.
• Paso el disco mayor del poste 1 al 3.
• Aplico P_2 para pasar los dos discos en el poste 2 al poste 3.
  Llamemos a este procedimiento $P_3$.

Solución para 4 discos

• Aplico P_3 para pasar los 3 discos superiores del poste 1 al poste 2.
• Paso el disco grande del poste 1 al poste 3.
• Aplico P_3 para pasar los 3 discos en el poste 2 al poste 3.
  Llamemos a este procedimiento $P_4$.

En general, si sabemos resolver las Torres de Hanoi para $ n $ discos, también lo sabemos resolver para $n+1$ discos. (A esta forma de razonar se le llama recursión. Ver mi post sobre ese tema en http://www.matetam.com/blog/entradas-jmd/dijiste-recursion

Epílogo

Fácil ¿no es cierto? Pues no. Porque una cosa es al teoría ¡y vámonos a la práctica! Por propia experiencia sé que no es fácil resolverlo para más de 3 discos en el mínimo número de movidas, incluso sabiendo la teoría. Este es un ejemplo de que el significado está en el uso. ("Las reglas del juego parecen muertas. ¿Qué les da vida? En el uso están vivas.")

Ahora bien ¿cuál es el número de movidas? Llamemos a ese número $T(n)$, para $ n $ discos. Sabemos que para $n=1,2,3,4$ se tiene que $T(n)=1,3,7,15$. ¿Cuál es el término n_ésimo?

Bueno, por lo que dijimos antes, debería ser claro que $T(n)=T(n-1)+1+T(n-1)=2T(n-1)+1.$

No es difícil conjeturar (a partir de los primeros términos 1,3,7,15) que el patrón es $T(n)=2^n-1$. Veamos si cumple la recursión:

$$T(n)=2^n-1=2^n-2+1=2[2^{n-1}-1]+1=2T(n-1)+1$$

Y se ve que la conjetura es correcta: las Torres de Hanoi se pueden resolver en $2^n-1$ movidas, con $ n $ discos.

Los saluda
jmd