Torres de Hanoi, continuación

Cuando resolviste las Torres de Hanoi para tres discos, tuviste que exponer el disco inferior, el disco 3, para poder moverlo de la varilla A a la varilla B. Para poder exponer el disco 3, tuviste que mover los discos 1 y 2 de la varilla A a la varilla libre, que es la varilla C:

Espera un minuto. Parece que se movieron dos discos en un solo paso, violando la primera regla. Pero no se movieron en un solo paso. Estuviste de acuerdo en que puedes mover los discos 1 y 2 de cualquier varilla a cualquier varilla, al usar tres pasos. La situación de arriba representa lo que tienes después de tres pasos. (Mueve el disco 1 de la varilla A a la varilla B; mueve el disco 2 de la varilla A a la varilla C; mueve el disco 1 de la varilla B a la varilla C).

Más al punto, al mover los discos 1 y 2 de la varilla A a la varilla C, resolviste un subproblema de manera recursiva: mover los discos del 1 al $n-1$‍ (recuerda que $n=3$‍) de la varilla A a la varilla C. Una vez que hayas resuelto este subproblema, puedes mover el disco 3 de la varilla A a la varilla B:

Ahora, para terminar, necesitas resolver de manera recursiva el subproblema de mover los discos del 1 al $n-1$‍ de la varilla C a la varilla B. Otra vez, estuviste de acuerdo en que puedes hacerlo en tres pasos. (Mueve el disco 1 de la varilla C a la varilla A; mueve el disco 2 de la varilla C a la varilla B; mueve el disco 1 de la varilla A a la varilla B). Y ya terminaste:

Y, sabías que venía esta pregunta, ¿hay algo especial acerca de las varillas a las cuales moviste los discos 1 al 3? Los podrías haber movido de cualquier varilla a cualquier varilla. Por ejemplo, de la varilla B a la varilla C:

No importa cómo lo dividas, puedes mover los discos del 1 al 3 de cualquier varilla a cualquier varilla, al mover los discos siete veces. Observa que mueves los discos tres veces por cada una de las dos veces que resuelves de manera recursiva el problema de mover los discos 1 y 2, más un movimiento adicional para el disco 3.

¿Qué pasa cuando $n=4$‍? Como puedes resolver de manera recursiva el subproblema de mover los discos 1 al 3 de cualquier varilla a cualquier varilla, puedes resolver el problem para $n=4$‍:

Esta solución mueve los discos 15 veces (7 + 1 + 7) y, sí, puedes mover los discos del 1 al 4 de cualquier varilla a cualquier varilla.

En este momento, puede que hayas detectado dos patrones . Primero, puedes resolver el problema de las Torres de Hanoi de manera recursiva. Si $n=1$‍, solo mueve el disco 1. De lo contrario, cuando $n\ge 2$‍, resuelve el problema en tres pasos:

En segundo lugar, resolver un problema para $n$‍ discos requiere $2^n-1$‍ movimientos. Ya vimos que eso es verdadero para:

Si puedes resolver un problema para $n-1$‍ discos en $2^{n-1}-1$‍ movimientos, entonces puedes resolver un problema para $n$‍ discos en $2^n-1$‍ movimientos. Necesitas:

Si sumas los movimientos, obtienes $2^n-1$‍.

De regreso a los monjes. Ellos están usando $n=64$‍ discos, así que necesitarán mover un disco $2^{64}-1$‍ veces. Estos monjes son ágiles y fuertes. Pueden mover un disco cada segundo, noche y día.

¿Cuánto es $2^{64}-1$‍ segundos? Al usar la estimación aproximada de 365.25 días por año, eso da 584,542,046,090.6263 años. Es es más de 584 mil millones de años. Al sol solo le quedan alrededor de otros cinco a siete mil millones de años antes de que se convierta en una supernova. Así que sí, el mundo se va a acabar, pero no importa qué tan tenaces sean los monjes, eso pasará mucho antes de que logren pasar todos los 64 discos a la varilla B.

¿Te estás preguntando de qué otra manera podemos usar este algoritmo, además de predecir el fin del mundo? Wikipedia tiene una lista con varias aplicaciones interesantes.

Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.