La Torre de Hanói de siempre tiene tres postes. ¿Qué pasa si añadimos uno y pasamos a cuatro? Las reglas son las mismas: se mueve un disco por turno, sin poner nunca un disco grande sobre uno pequeño, para llevar la torre a otro poste.
Con solo un poste más, los movimientos bajan mucho
Con un sitio más donde dejar discos, apartarlos es mucho más fácil. Si comparas el mínimo de movimientos, la diferencia crece con el número de discos.
| Discos | Con 3 postes | Con 4 postes |
|---|---|---|
| 3 | 7 | 5 |
| 4 | 15 | 9 |
| 5 | 31 | 13 |
| 6 | 63 | 17 |
| 7 | 127 | 25 |
| 8 | 255 | 33 |
| 10 | 1023 | 49 |
| 64 | unos 18,4 trillones | 18.433 |
Con tres postes, mover 64 discos lleva unos 584 500 millones de años a un movimiento por segundo (¿Cuántos años se tardaría en mover 64 discos?). Con cuatro postes son 18.433 movimientos, es decir, unas 5 horas a un movimiento por segundo. Si los monjes de la leyenda hubieran añadido un poste, el mundo se habría acabado ese mismo día.
El «rompecabezas del queso» de Dudeney
Quien dio a conocer ampliamente la Torre de Hanói con cuatro postes fue el autor de pasatiempos británico Henry Dudeney. En su libro de 1907 «Los rompecabezas de Canterbury» (The Canterbury Puzzles) la planteó como «el rompecabezas de Reve». Reve (Reeve) era el administrador de una hacienda.
En el problema de Dudeney, en lugar de discos hay ocho quesos de distintos tamaños que se mueven entre cuatro taburetes. No se puede poner un queso grande sobre uno pequeño. La respuesta son 33 movimientos, igual que en la fila de 8 discos de la tabla de arriba.
El método de Frame y Stewart
Para mover con pocos movimientos con cuatro postes, en 1941 J. S. Frame y B. M. Stewart publicaron, cada uno por su lado, la misma idea. Para mover una torre de n discos, se divide en tres pasos:
- Mover los k discos de arriba, usando los cuatro postes, a uno de los postes que no es el de destino.
- Mover los n−k discos restantes al poste de destino usando solo tres postes, sin usar el poste donde están los k discos (2ⁿ⁻ᵏ−1 movimientos).
- Mover los k discos apartados en el paso 1, usando los cuatro postes, al poste de destino.
Los pasos 1 y 3 son versiones más pequeñas del mismo problema, así que sirve la idea de la recursión (artículo sobre el algoritmo). Solo queda elegir cuántos discos (k) dejar arriba para que el total sea el mínimo. Con 8 discos, lo mejor es apartar primero los 4 o 5 de arriba, y salen 33 movimientos.
El «mínimo» que casi un siglo después no se había demostrado
Se sabía que el método de Frame y Stewart mueve la torre con pocos movimientos. Pero durante mucho tiempo nadie pudo demostrar que no existiera un método con menos movimientos.
Con tres postes, el mínimo se demuestra enseguida a partir de un solo hecho: «en el momento de mover el disco más grande, todos los demás discos tienen que estar juntos en un poste» (fórmula del mínimo de movimientos). Con cuatro postes, en el momento de mover el disco grande los demás pueden estar repartidos de cualquier manera entre los otros dos postes, así que las secuencias posibles se multiplican de golpe.
Con ordenadores se revisaron todas las posiciones y se comprobó que este método era el mínimo hasta unos 30 discos. Y en 2014, unos 100 años después del problema de Dudeney, el matemático francés Thierry Bousch demostró que el método de Frame y Stewart es el mínimo con cualquier número de discos. Con cinco o más postes, se dice que todavía no está demostrado.
Pruébalo tú
Con la Torre de Hanói de cuatro postes puedes hacerla con el método de cartulina del artículo sobre cómo hacerla, dibujando cuatro círculos como sitios donde dejar los discos. Prueba a mover 3 discos en 5 movimientos y 4 en 9. Sentirás con las manos la diferencia con tres postes.
