Cómo resolver las Torres de Hanói

Cuaderno de bitácora: gracias a la guía de nuestro compañero matenavegante Pablo Viedma, un día pudimos visitar, en nuestro periplo mateoceánico, las Torres de Hanói.

Este juego fue inventado en el año 1883 por un matemático francés, Edouard Lucas. Se trata de un solitario que se compone de tres pivotes o estacas verticales insertadas en un tablero y una pila con un cierto número de discos de tamaños crecientes, normalmente siete u ocho.

Figura 1.

El juego consiste en trasladar la pila entera de discos de uno de los pivotes a cualquiera de los otros dos, pero teniendo en cuenta las reglas:

-Sólo se puede tomar un disco en cada movimiento.
-El disco tiene que estar en la posición superior de su pila.
-Al pasarlo a otro pivote no se puede colocar sobre otro disco más pequeño.

Edouard Lucas, para dar mayor interés y contexto al juego, se inventó la leyenda de que el juego se había creado en un templo de Benarés, en la India, hoy ya desaparecido. Según esa leyenda, allí se comenzó con una Torre de 64 discos apilados.

Es fácil calcular el número mínimo de movimientos necesarios para trasladar toda la torre de una varilla a otra: 2ⁿ − 1, siendo n el número de discos que hay en la torre.

Si por ejemplo tenemos una torre de 8 discos, como en la figura 1, el número mínimo de movimientos será de:

2⁸ − 1 = 256 − 1 = 255 movimientos.

En el caso de la leyenda del templo de Benarés, para mover toda la torre de 64 discos de un pivote a otro, se necesitarían:

2⁶⁴ − 1 = 18.446.744.073.709.551.615 movimientos como mínimo, más de 18 trillones.

Con un sencillo cálculo se puede comprobar que si hiciéramos un movimiento por segundo harían falta 584.942.417.355 años para completar todo el traslado.

El número total de movimientos para 64 discos nos recuerda otra leyenda famosa en matemáticas, la del inventor del ajedrez. Se dice que cuando el inventor presentó el ajedrez a su rey, este le ofreció como premio cualquier cosa que pidiera. El inventor pidió un grano de trigo por la primera casilla del tablero de ajedrez, dos granos de trigo por la segunda casilla, cuatro por la tercera, ocho por la cuarta, y así sucesivamente, doblando la cantidad de granos en cada casilla hasta completar las 64 de todo el tablero. Si calculamos el número de granos de trigo que hay que reunir en total nos sale exactamente la misma cantidad que los movimientos de la torre de 64 discos:

2⁶⁴ - 1 = 18.446.744.073.709.551.615 granos de trigo. (Para más información, consultar la entrada Leyenda sobre el tablero de ajedrez)

Hay estudios matemáticos muy completos sobre las Torres de Hanói. Es realmente interesante conocer la relación que existe entre las posiciones de los discos y los números del sistema binario. Otra actividad muy interesante para los grumetes es investigar en qué movimiento se mueve cada disco, y obtener así diversas progresiones aritméticas. Quizás dediquemos entradas futuras a tratar estos dos aspectos.

Pero enfrentémonos al juego e intentemos resolverlo. Nos daremos cuenta de que si los discos son muy pocos, dos, tres, hasta cuatro, trasladar la torre es sencillo. Pero a partir de cinco, seis discos... la cosa se empieza a poner complicada, el número de movimientos crece rápidamente y es muy fácil perderse.

Para ello hay dos trucos, cualquiera de los dos ayudan por separado a resolver el puzle, y si los combinamos entonces no podemos perdernos.

-El primer truco consiste en pintar los discos en dos colores diferentes, alternados, por ejemplo blanco y negro. También debemos pintar las bases de los pivotes en colores alternados: los pivotes libres uno debe ser negro de base y el otro blanco, y el pivote de partida debe tener el color contrario al disco más grande. Cuando tengamos pintados los discos y las bases debemos añadir una nueva regla: cada disco que movamos debe colocarse sobre otro disco o base de color contrario, nunca del mismo color.

-El segundo truco consiste en fijarse en que  el disco más pequeño, el que inicialmente está en la cúspide de la torre, se mueve en el movimiento 1º, 3º, 5º, 7º, 9º, ... en todos los movimientos impares. Empezamos moviendo el disco pequeño, movemos otro disco, luego otra vez el pequeño, luego otro disco, luego el pequeño otra vez, luego otro disco, luego el pequeño, y así sucesivamente. De cada dos discos que movemos, uno es el pequeño.

Además, siempre debemos mover el disco pequeño en el mismo sentido. Entre los pivotes hay dos sentidos de movimiento: el que podemos llamar sentido positivo o de izquierda a derecha, 1→2→3→1, y el que podemos llamar sentido negativo o de derecha a izquierda, 3→2→1→3.

Vamos a emplear este segundo truco o procedimiento para resolver este solitario. Haremos el ejemplo de una torre con 4 discos.

Figura 2.

A continuación ponemos la secuencia completa de 2⁴ − 1 = 15 movimientos:

movimiento 1º: a1 → 2
movimiento 2º: b1 → 3
movimiento 3º: a2 → 3
movimiento 4º: c1 → 2
movimiento 5º: a3 → 1
movimiento 6º: b3 → 2
movimiento 7º: a1 → 2
movimiento 8º: d1 → 3
movimiento 9º: a2 → 3
movimiento 10º: b2 → 1
movimiento 11º: a3 → 1
movimiento 12º: c2 → 3
movimiento 13º: a1 → 2
movimiento 14º: b1 → 3
movimiento 15º: a2 → 3

Veamos los movimientos en una secuencia de fotografías:

Figura 3.
 a1 → 2

Figura 4.
 b1 → 3

Figura 5.
a2 → 3

Figura 6.
c1 → 2

Figura 7.
a3 → 1

Figura 8.
b3 → 2

Figura 9.
a1 → 2

Figura 10.
d1 → 3

Figura 11.
a2 → 3

Figura 12.
b2 → 1

Figura 13.
a3 → 1

Figura 14.
c2 → 3

Figura 15.
a1 → 2

Figura 16.
b1 → 3

Figura 17.
a2 → 3 y final.

Obsérvese que:

-El disco más pequeño, el a, siempre se ha movido de izquierda a derecha y en los movimientos impares, es decir, cada 2 movimientos.
-El segundo disco, el b, se ha movido de derecha a izquierda; se movió en el 2º movimiento y luego cada 4 movimientos (en el 6º, el 10º y el 14º).
-El tercer disco, el c, se ha movido como el a, de izquierda a derecha, empezando en el 4º movimiento y luego cada 8 movimientos (en el 12º).
-El cuarto disco, el d, se ha movido como el b, de derecha a izquierda, empezando en el 8º movimiento y luego le tocaba moverse cada 16 movimientos, pero como en nuestro ejemplo no había más que 15 movimientos, este disco sólo se ha movido una vez.

Con este ejemplo creemos que el lector puede guiarse para resolver el pasatiempo cuando la torre tiene más discos, aunque conforme el número de discos aumenta, el número de movimientos aumenta exponencialmente, y es difícil no perder la atención y confundirse en cualquier momento.