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.
- Llevar los n discos de arriba de A a B: como mínimo aₙ movimientos.
- Mover el disco n+1 de A a C: 1 movimiento.
- 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:
- 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.
- 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.
- 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.
- Llevar los n−1 discos de arriba de A a C: bₙ₋₁ movimientos (para mover n a B hay que dejar B vacío).
- Mover el disco n de A a B: 1 movimiento.
- Llevar los n−1 discos de C a A: bₙ₋₁ movimientos (para mover n a C hay que dejar C vacío).
- Mover el disco n de B a C: 1 movimiento.
- 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.
- Halla el mínimo de movimientos con 10 discos.
- ¿Con cuántos discos se supera por primera vez los 1000 movimientos mínimos?
- 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).
