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:
Movimiento 1 de las Torres de Hanoi, 3 discos
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 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, minus, 1 (recuerda que n, equals, 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:
Movimiento 2 de las Torres de Hanoi, 3 discos
Ahora, para terminar, necesitas resolver de manera recursiva el subproblema de mover los discos del 1 al n, minus, 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:
Movimiento 3 de las Torres de Hanoi, 3 discos
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, equals, 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, equals, 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, equals, 1, solo mueve el disco 1. De lo contrario, cuando n, is greater than or equal to, 2, resuelve el problema en tres pasos:
  • Resuelve de manera recursiva el subproblema de mover los discos del 1 al n, minus, 1 de cualquier varilla en donde empiecen a la varilla libre.
  • Mueve el disco 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 n, minus, 1 de la varilla libre a la varilla en la que deben terminar.
En segundo lugar, resolver un problema para n discos requiere 2, start superscript, n, end superscript, minus, 1 movimientos. Vimos que es cierto para n, equals, 1 (2, start superscript, 1, end superscript, minus, 1, equals, 1, y necesitamos un movimiento), n, equals, 2 (2, start superscript, 2, end superscript, minus, 1, equals, 3, y tres movimientos), n, equals, 3 (2, start superscript, 3, end superscript, minus, 1, equals, 7, y siete movimientos), y n, equals, 4 (2, start superscript, 4, end superscript, minus, 1, equals, 15, y 15 movimientos). Si puedes resolver un problema para n, minus, 1 discos en 2, start superscript, n, minus, 1, end superscript, minus, 1 movimientos, entonces puedes resolver un problema para n discos en 2, start superscript, n, end superscript, minus, 1 movimientos: necesitas 2, start superscript, n, minus, 1, end superscript, minus, 1 movimientos para resolver de manera recursiva el primer subproblema de mover los discos del 1 al n, minus, 1, uno para mover el disco n, y otros 2, start superscript, n, minus, 1, end superscript, minus, 1 movimientos para resolver de manera recursiva el segundo subproblema de mover los discos del 1 al n, minus, 1. Si sumas los movimientos, obtienes 2, start superscript, n, end superscript, minus, 1.
De regreso a los monjes. Están usando n, equals, 64 discos, así que tendrán que mover un disco 2, start superscript, 64, end superscript, minus, 1 veces. Estos monjes son ágiles y fuertes. Pueden mover un disco cada segundo, día y noche. ¿Cuánto tiempo es 2, start superscript, 64, end superscript, minus, 1 segundos? Al usar la estimación aproximada de 365.25 días al año (no estamos contabilizando saltarnos el año bisiesto cada 400 años), eso es 584,542,046,090.6263 años. Eso es más de 584 mil millones de años. Al sol le quedan entre cinco y siete mil millones de años antes de que se haga una supernova. Así que, sí, el mundo se acabará, pero no importa qué tan tenaces sean los monjes, pasará mucho tiempo antes de que puedan 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.