Con n discos, el mínimo de movimientos para llevar la torre a otro poste en la Torre de Hanói es 2ⁿ−1. Es el número que sale al multiplicar 2 por sí mismo tantas veces como discos y restar 1.

Número de discosMínimo de movimientos
11
23
37
415
531
663
7127
8255
9511

Cada disco que se añade casi duplica los movimientos. Veamos por qué, paso a paso.

Fíjate en el disco más grande

Piensa en llevar una torre de n discos de la izquierda a la derecha. El disco más grande está debajo de todos los demás, así que no se puede mover tal cual. Para llevarlo a la derecha, en ese momento tiene que cumplirse lo siguiente:

  • No hay nada encima del disco grande.
  • El poste derecho está vacío (porque un disco más pequeño que el grande no puede estar debajo de él).

Es decir, los otros n−1 discos tienen que estar todos apilados en el poste central.

Los movimientos se dividen en tres partes

Por tanto, la secuencia para mover n discos se divide en tres partes:

  1. Llevar los n−1 discos de arriba de la izquierda al centro.
  2. Mover el disco más grande de la izquierda a la derecha, en un solo movimiento.
  3. Llevar los n−1 discos del centro a encima del disco grande.

Las partes 1 y 3 son exactamente el problema de «mover una torre de n−1 discos». Si escribimos T(n) para el mínimo de movimientos con n discos, tenemos la relación

T(n) = T(n−1) + 1 + T(n−1) = 2 × T(n−1) + 1

Con 1 disco son 1 movimiento, así que T(1) = 1. A partir de ahí salen 3, 7, 15, 31…

Por qué la fórmula es 2ⁿ−1

Si sumas 1 a los dos lados de esta relación, queda

T(n) + 1 = 2 × (T(n−1) + 1)

Es decir, «los movimientos más 1» se duplican exactamente cada vez que se añade un disco. Con 1 disco, T(1) + 1 = 2, así que con n discos es 2 multiplicado n veces, es decir, 2ⁿ. Restando 1, T(n) = 2ⁿ−1.

Por qué no se puede hacer con menos

Hemos visto que con la secuencia anterior se puede mover la torre en 2ⁿ−1 movimientos. ¿No habrá un método con menos?

Como hemos visto, en el momento de mover por primera vez el disco grande, los otros n−1 discos tienen que estar todos apilados en un mismo poste distinto. Hasta ese momento hacen falta al menos los movimientos de mover una torre de n−1 discos. De la misma manera, después de dejar el disco grande a la derecha por última vez, volver a apilar encima los otros n−1 discos también requiere al menos los movimientos de mover una torre de n−1 discos. Y el propio disco grande se mueve al menos una vez.

Cualquier secuencia necesita siempre estas tres partes. Por eso no se puede hacer con menos de 2 × T(n−1) + 1 movimientos. Además, se sabe que la secuencia mínima es, en realidad, única.

En el «Clásico» de la app son 127 movimientos

El modo «Clásico» de la app «Torre de Hanói» usa 7 discos, así que el mínimo es 2⁷−1 = 127 movimientos. Si llegas a 127 movimientos, lo has resuelto con la secuencia mínima. Si mueves el disco pequeño siempre en el mismo sentido, como se explica en el artículo sobre cómo jugar, lo completas en exactamente 127 movimientos.