La Torre de Hanói aparece a menudo en libros de texto y exámenes de acceso como tema de recurrencias y de inducción matemática (en Japón, en las matemáticas de bachillerato). En este artículo practicamos la manera de pensar resolviendo ejemplos. Los discos van numerados 1, 2, 3… de menor a mayor, y el mínimo de movimientos para mover una torre de n discos se escribe aₙ.

Ejemplo 1: plantear la recurrencia

Problema: Hay tres postes A, B y C, y en A hay n discos de distintos tamaños apilados de mayor a menor. Se mueve un disco cada vez, sin poner nunca un disco grande sobre uno pequeño, hasta llevar todos los discos a C. Si el mínimo de movimientos es aₙ, expresa aₙ₊₁ en función de aₙ.

Solución: Fíjate en el disco más grande (el número n+1). Para moverlo a C, en ese momento los n discos de arriba tienen que estar todos apilados en B.

  1. Llevar los n discos de arriba de A a B: como mínimo aₙ movimientos.
  2. Mover el disco n+1 de A a C: 1 movimiento.
  3. Llevar los n discos de B a C: como mínimo aₙ movimientos.

Con esta secuencia se mueven n+1 discos, así que aₙ₊₁ ≤ 2aₙ + 1. Y al revés, cualquier secuencia necesita siempre los movimientos de 1 a 3, así que aₙ₊₁ ≥ 2aₙ + 1. Por tanto,

aₙ₊₁ = 2aₙ + 1 (a₁ = 1)

En los exámenes a veces se pide demostrar tanto «≤» como «≥» para afirmar la igualdad. La explicación detallada está en la fórmula del mínimo de movimientos.

Ejemplo 2: hallar el término general

Problema: Halla el término general de la sucesión definida por a₁ = 1 y aₙ₊₁ = 2aₙ + 1.

Solución: Una recurrencia de la forma aₙ₊₁ = paₙ + q se transforma usando el α que cumple α = 2α + 1. Como α = −1, sumando 1 a los dos lados,

aₙ₊₁ + 1 = 2(aₙ + 1)

La sucesión aₙ + 1 es una progresión geométrica de primer término a₁ + 1 = 2 y razón 2. Por tanto, aₙ + 1 = 2 · 2ⁿ⁻¹ = 2ⁿ, y

aₙ = 2ⁿ − 1

Para comprobarlo, verifica que a₁ = 1, a₂ = 3 y a₃ = 7 coinciden con la recurrencia.

Ejemplo 3: demostrar por inducción matemática

Problema: Demuestra por inducción matemática que el mínimo de movimientos para mover n discos es 2ⁿ − 1.

Solución:

  1. Con n = 1, un disco se mueve en 1 movimiento y no se puede en menos, así que el mínimo es 1 = 2¹ − 1 y se cumple.
  2. Supón que con n = k el mínimo es 2ᵏ − 1. Con n = k+1, por la idea del ejemplo 1, el mínimo es 2(2ᵏ − 1) + 1 = 2ᵏ⁺¹ − 1, así que también se cumple con n = k+1.
  3. Por 1 y 2, se cumple para todo número natural n.

Lo importante es que el «≤ y ≥ a la vez» del ejemplo 1 se usa en el paso 2 de la inducción.

Ejemplo 4: cuando solo se puede mover a un poste vecino

Problema: Los postes A, B y C están en fila, y los discos solo se pueden mover entre A y B, y entre B y C (de A a C no se puede mover directamente). Halla el mínimo de movimientos bₙ para llevar n discos de A a C.

Solución: El disco más grande, el n, tiene que moverse dos veces: A → B → C.

  1. Llevar los n−1 discos de arriba de A a C: bₙ₋₁ movimientos (para mover n a B hay que dejar B vacío).
  2. Mover el disco n de A a B: 1 movimiento.
  3. Llevar los n−1 discos de C a A: bₙ₋₁ movimientos (para mover n a C hay que dejar C vacío).
  4. Mover el disco n de B a C: 1 movimiento.
  5. Llevar los n−1 discos de A a C: bₙ₋₁ movimientos.

Por tanto, bₙ = 3bₙ₋₁ + 2 (b₁ = 2). De α = 3α + 2 sale α = −1, así que bₙ + 1 = 3(bₙ₋₁ + 1). La sucesión bₙ + 1 es una progresión geométrica de primer término 3 y razón 3, así que

bₙ = 3ⁿ − 1

También se ha comprobado, con un cálculo que revisa todas las disposiciones para de 1 a 6 discos, que este es el mínimo de movimientos. Curiosamente, durante los 3ⁿ − 1 movimientos se pasa exactamente una vez por cada una de las 3ⁿ disposiciones posibles (el número de disposiciones está en el artículo sobre regularidades).

Ejemplo 5: problemas de práctica

Para terminar, resuélvelos tú. Las respuestas están abajo.

  1. Halla el mínimo de movimientos con 10 discos.
  2. ¿Con cuántos discos se supera por primera vez los 1000 movimientos mínimos?
  3. Al mover n discos con la secuencia mínima, ¿cuántas veces se mueve el disco más pequeño?

Respuestas: 1. 2¹⁰ − 1 = 1023 movimientos. 2. De 2ⁿ − 1 > 1000 sale 2ⁿ > 1001; como 2⁹ = 512 y 2¹⁰ = 1024, con 10 discos o más. 3. 2ⁿ⁻¹ veces (la razón está en «Cuántas veces se mueve cada disco» del artículo sobre regularidades).