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 n1 n-1 (recuerda que n=3 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 n1 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:
  • Resuelve de manera recursiva el subproblema de mover los discos 1 y 2 de la varilla B a la varilla libre, la varilla A. (Mueve el disco 1 de la varilla B a a varilla C; mueve el disco 2 de la varilla B a la varilla A; mueve el disco 1 de la varilla C a la varilla A).
  • Ahora que el disco 3 está expuesto en la varilla B, muévelo a la varilla C.
  • Resuelve de manera recursiva el subproblema de mover los discos 1 y 2 de la varilla A a la varilla C. (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).
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 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 n = 4 :
  • Resuelve de manera recursiva el subproblema de mover los discos del 1 al 3 de la varilla A a la varilla C, al mover los discos siete veces.
  • Mueve el disco 4 de la varilla A a la varilla B.
  • Resuelve de manera recursiva el subproblema de mover los discos del 1 al 3 de la varilla C a la varilla B, al mover los discos siete veces.
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 n = 1 , solo mueve el disco 1. De lo contrario, cuando n2 n \geq 2 , resuelve el problema en tres pasos:
  • Resuelve de manera recursiva el subproblema de mover los discos del 1 al n1 n-1 de cualquier varilla en donde empiecen a la varilla libre.
  • Mueve el disco n n de la varilla en donde empieza a la varilla en la que debe terminar.
  • Resuelve de manera recursiva el subproblema de mover los discos del 1 al n1 n-1 de la varilla libre a la varilla en la que deben terminar.
En segundo lugar, resolver un problema para n n discos requiere 2n1 2 ^ n - 1 movimientos. Ya vimos que eso es verdadero para:
  • n=1 n = 1 (211=1 2^1 - 1 = 1 , solo se necesitó un movimiento)
  • n=2 n = 2 (221=3 2^2 - 1 = 3 , se necesitaron tres movimientos)
  • n=3 n = 3 (231=7 2^3 - 1 = 7 , se necesitaron siete movimientos)
  • n=4 n = 4 (241=15 2^4 - 1 = 15 , se necesitaron 15 movimientos).
Si puedes resolver un problema para n1 n-1 discos en 2n11 2 ^{n-1} - 1 movimientos, entonces puedes resolver un problema para n n discos en 2n1 2 ^ n - 1 movimientos. Necesitas:
  • 2n11 2^{n-1} - 1 movimientos para resolver de manera recursiva el primer subproblema de mover los discos 1 a n1 n-1
  • 11 movimiento para mover el disco n n
  • 2n11 2^{n-1} - 1 movimientos (de nuevo) para resolver de manera recursiva el segundo subproblema de mover los discos 1 a n1 n-1
Si sumas los movimientos, obtienes 2n1 2^n - 1 .
De regreso a los monjes. Ellos están usando n=64 n = 64 discos, así que necesitarán mover un disco 2641 2^{64} - 1 veces. Estos monjes son ágiles y fuertes. Pueden mover un disco cada segundo, noche y día.
¿Cuánto es 2641 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.
Cargando