Si quieres saber cómo resolver el problema de las torres de Hanoi, puedes alardear de una cabeza prodigiosa o memoria con este método ¡no hace falta un ordenador! Podrías proponerte batir el record Guiness en número de piezas en el menor tiempo posible.

  1. Si el número de piezas es par, hay que seguir la secuencia 3-4-5 (3,4,5,3,4,5,3,4,5…)
  2. Y si el número de piezas en impar, hay que seguir la secuencia 4-3-5 (4,3,5,4,3,5,4,3,5…)

Así de simple.

Yo llamo a la primera base origen “1″, a la intermedia “2″ y a la final “3″ El movimiento “3″ significa (3=1+2) mover de 1 a 2 o de 2 a 1. El movimiento “4″ (4=1+3) significa mover de la 1 a la 3 o de la 3 a la 1. Y el movimiento “5″ (5=2+3) mover de 2 a 3 o de 3 a 2.
¿Qué movimiento elegir? Pues la pieza menor se pone encima de la mayor. No hay confusión.

¿Hasta cuando hay que parar? Está claro, cuando la pirámide mayor esté en la base 3. En 2^n - 1 movimientos.

La demostración es sencilla. La dejo para el final.

Esto lo descubrí en 1988, en el colegio. Nuestro profesor de informática, D. Enrique Álvarez, sin habernos explicado la recurrencia (y sin explicar programación) nos pidió un programa que resolviera el problema de las torres de Hanoi. Yo sabía programar gracias a mi Spectrum 48K. Fui uno de los pocos en resolverlo (creo que el único) Y cuando orgulloso le digo que lo había resuelto, él, en primer lugar no quiso verlo, después me preguntó

-Para 10 piezas, ¿en cuantos movimientos lo resuelves?

Sabía la respuesta ya que me había “cultivado” en el problema. Eran 1023 (2 elevado a 10 menos uno) Pero tardé un poco, como pensándomelo.

“1023 movimientos” Le respondí. Él sacó una calculadora de su bata blanca (creo que fue el primero en iniciar la moda en mi colegio, a lo de la bata, me refiero) y me dijo:

-Se puede hacer en menos.

Y se quedó tan pancho. Excitado, le intenté demostrar que era la solución mínima. Se dio la vuelta y exclamó “Felipe se ha enfadado” mientras se alejaba por el pasillo.

He aquí la demostración.

Antes aclarar que 2^{2n} \mod 3 = 1 y que 2^{2n+1} \mod 3 = 2 Y eso es también fácil de demostrar. Lo dejo para el lector.

Caso base. Con una pieza (impar), el movimiento único va de la “1″ a la “3″ -> {1-3} -> {(1+3)} -> {4}

Con dos piezas (par), los movimientos son {1-2, 1-3, 2-3} -> {(1+2),(1+3),(2+3)} -> {3,4,5}

Con el número de piezas par. Movemos la pirámide de tamaño n-1 de la base 1 a la base 2. Por hipótesis de inducción, los movimientos para n-1 (que es impar) son 4-3-5, pero como hay que pasar de la 1 a la 2 (cambiamos la base 3 por la 2) y el movimiento 4 (1+3) se transforma en (1+2) = 3, el movimiento 3 (1+2) en 4 (1+3), y el movimiento 5 (2+3) en 5 (3+2). Por ahora llevamos la secuencia 3-4-5 correctamente. La pirámide n-1 se mueve en 2^{n-1} - 1 movimientos. Como n-1 es impar la secuencia acaba en 3 (2^{2m-1} - 1 \mod 3 = 2 - 1 = 1) Movemos la pieza más grande de la 1 a la 3 (movimiento 4 (1+3)) y la pirámide n-1 de la 2 a la 3, hay que seguir la secuencia 4-3-5 pero intercambiando las bases 1 por la 2. Con lo que continuamos con la secuencia 5-3-4. Es decir {3-4-5- … -5-3} {4} {5-3-4-5 … }

El número de piezas impar. Prácticamente igual, copio y pego. Movemos la pirámide de tamaño n-1 de la base 1 a la base 2. Por hipótesis de inducción, los movimientos para n-1 (que es par) son 3-4-5, pero como hay que pasar de la 1 a la 2 (cambiamos la base 3 por la 2) y el movimiento 3 (1+2) se transforma en (1+3) = 4, el movimiento 4 (1+3) en 3 (1+2), y el movimiento 5 (2+3) en 5 (3+2). Por ahora llevamos la secuencia 4-3-5 correctamente. La pirámide n-1 se mueve en 2^{n-1} - 1 movimientos. Como n-1 es par la secuencia acaba en 5 (2^{2m} - 1 \mod 3 = 1 - 1 = 0) Movemos la pieza más grande de la 1 a la 3 (movimiento 4 (1+3)) y la pirámide n-1 de la 2 a la 3, hay que seguir la secuencia 3-4-5 pero intercambiando las bases 1 por la 2. Con lo que continuamos con la secuencia 3-5-4. Es decir {4-3-5- … -3-5} {4} {3-5-4-3 … }

Chupao!!