Si resuelves la Torre de Hanói con el mínimo de movimientos, la secuencia tiene regularidades sorprendentemente bellas. Aquí te presento, una a una, las reglas que aparecen en la secuencia mínima (2ⁿ−1 movimientos) para llevar una torre de n discos de la izquierda a la derecha. Los discos van numerados 1, 2, 3… de menor a mayor.
Cada disco se mueve una potencia de 2 de veces
En la secuencia mínima, el número de veces que se mueve cada disco está fijado. Con n discos, el disco número k se mueve 2ⁿ⁻ᵏ veces.
| Disco (con 4 discos) | Veces que se mueve |
|---|---|
| 1 | 8 |
| 2 | 4 |
| 3 | 2 |
| 4 | 1 |
| Total | 15 |
El disco más grande se mueve 1 vez, el siguiente 2, el siguiente 4… y al hacerse más pequeño se duplica cada vez. La suma es 1 + 2 + 4 + … + 2ⁿ⁻¹ = 2ⁿ−1, que coincide exactamente con el mínimo de movimientos.
La razón se entiende con la misma idea de la fórmula del mínimo de movimientos. Para mover n discos, se mueve dos veces una torre de n−1 discos. Por eso los discos más pequeños que el n se mueven el doble de veces que al mover n−1 discos.
Qué disco se mueve en cada movimiento
En la secuencia mínima con 4 discos, si escribes en orden, desde el primer movimiento, el número del disco que se mueve, sale esto:
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
El 1 aparece cada dos movimientos, entre ellos el 2 aparece uno de cada dos huecos, entre esos aparece el 3… Es la misma forma que la sucesión de longitudes de las marcas de una regla (corta, mediana, corta, larga…).
Esta sucesión se obtiene enseguida si escribes el número del movimiento en binario.
| Movimiento | Binario | Ceros al final | Disco que se mueve |
|---|---|---|---|
| 1 | 1 | 0 | 1 |
| 2 | 10 | 1 | 2 |
| 3 | 11 | 0 | 1 |
| 4 | 100 | 2 | 3 |
| 5 | 101 | 0 | 1 |
| 6 | 110 | 1 | 2 |
| 7 | 111 | 0 | 1 |
| 8 | 1000 | 3 | 4 |
En el movimiento m se mueve el disco número «(cantidad de ceros al final de m en binario) + 1». En los movimientos impares, el binario termina en 1, así que siempre se mueve el 1. Esa es la razón de que «en los movimientos impares se mueve el 1» del artículo sobre cómo resolverlo.
Además, los postes de origen y de destino también se obtienen solo con cálculos en binario (artículo sobre el algoritmo).
La relación con el código Gray
Al contar en binario desde 0, el número de cifras que cambian al sumar 1 varía (de 0111 a 1000 cambian 4 cifras). Una forma de escribir los números ordenados de modo que en cada paso cambie una sola cifra se llama «código Gray».
| Orden | Código Gray | Cifra que cambia (desde la derecha) |
|---|---|---|
| 0 | 000 | ― |
| 1 | 001 | 1 |
| 2 | 011 | 2 |
| 3 | 010 | 1 |
| 4 | 110 | 3 |
| 5 | 111 | 1 |
| 6 | 101 | 2 |
| 7 | 100 | 1 |
La sucesión de cifras que cambian, «1 2 1 3 1 2 1», es exactamente la misma que la de los discos que se mueven en la Torre de Hanói. Si piensas que cada disco es una cifra binaria y que «cambia esa cifra = se mueve ese disco», la secuencia mínima de la Torre de Hanói equivale a recorrer el código Gray en orden.
El sentido en que giran los discos
En el artículo sobre cómo resolverlo vimos que el 1 siempre gira en el mismo sentido. En realidad, los demás discos tienen la misma regla.
- Los discos de número impar (1, 3, 5…) giran todos en el mismo sentido que el 1.
- Los discos de número par (2, 4, 6…) giran todos en el sentido contrario al del 1.
Al llevar la torre de la izquierda a la derecha, con un número impar de discos el 1 sigue el sentido «izquierda → derecha → centro», y con un número par, «izquierda → centro → derecha». Ningún disco cambia nunca de sentido hasta el final.
Hay otra regla, la que vimos en cómo resolver 10 discos: en la secuencia mínima, nunca se pone directamente un disco impar sobre uno impar ni uno par sobre uno par.
En total hay 3ⁿ disposiciones
¿Cuántas disposiciones de los discos respetan las reglas? Cada disco puede estar en cualquiera de los 3 postes, y el orden de los discos de un mismo poste queda fijado, de mayor a menor, así que hay 3ⁿ disposiciones.
| Discos | Disposiciones |
|---|---|
| 3 | 27 |
| 5 | 243 |
| 7 | 2187 |
| 9 | 19.683 |
Además, de cualquier disposición se puede pasar a cualquier otra respetando las reglas. También se sabe que, si representas todas las disposiciones con puntos y unes con líneas los puntos que se alcanzan en un movimiento, sale una figura muy parecida al «triángulo de Sierpiński», con triángulos pequeños anidados dentro de uno grande.
El modo «Problemas» de la app «Torre de Hanói» crea sus problemas, que consisten en igualar un modelo, a partir de todas estas disposiciones. Incluso en ★5, con 9 discos, plantea los problemas después de calcular el mínimo de movimientos para cada una de las 19.683 disposiciones.
