Torres de Hanoi, la danza del mínimo movimiento

Imagen de BehindTheTmuna extraída de Unsplash

Las Torres de Hanói es uno de los pasatiempos matemáticos y computacionales más emblemáticos de la historia. Fue inventado en 1883 por el matemático francés Édouard Lucas, quien lo acompañó de un trasfondo mítico: la Leyenda del Templo de Benares.

Según la historia, los sacerdotes del templo custodian tres agujas de diamante con 64 discos de oro de distintos tamaños. Su tarea es trasladar toda la torre desde la primera aguja hasta la tercera siguiendo unas reglas sagradas e inalterables. Se dice que cuando completen el último movimiento, el templo se derrumbará y llegará el fin del mundo.

Detrás de esta narrativa mística se esconde una estructura matemática fascinante basada en la recursividad, la combinatoria de estados y el crecimiento exponencial.

Descripción formal del problema

El juego consta de 3 varillas verticales (denominadas A, B y C) y un conjunto de $n$ discos de diámetros decrecientes superpuestos inicialmente en la varilla A (origen), ordenados del más grande en la base al más pequeño en la cima.

El objetivo consiste en trasladar toda la pila de discos desde la varilla origen A hasta la varilla destino C, siguiendo las siguientes reglas:

1. En cada paso sólo se puede mover un único disco.
2. Un movimiento consiste en tomar el disco situado en la cima de una de las varillas y colocarlo en la cima de otra varilla o en una varilla vacía.
3. Jamás se puede colocar un disco sobre otro de menor tamaño.

Para analizar las propiedades de este juego, nos centraremos en el caso de $n = 3$ discos:

¿Sabrías decir cuál es el número mínimo de movimientos necesarios para completar el juego con 3 discos y cómo realizar la secuencia perfecta?

---

Solución del reto

Para resolver una torre de $n$ discos de la varilla A a la C, la estrategia óptima exige dividir el problema en tres sub-tareas recursivas:

1. Mover los $n-1$ discos superiores desde A hasta la varilla auxiliar B.
2. Mover el disco restante (el más grande, $n$) directamente de A a C.
3. Mover los $n-1$ discos desde la varilla auxiliar B a la varilla destino C.

Esto genera la relación de recurrencia para el número mínimo de movimientos $T(n)$ pudiéndose obtener la fórmula exacta de movimientos mínimos:

\[T(n) = 2^n - 1\]

Para nuestro caso de $n = 3$ discos, el número mínimo de movimientos es $2^3 - 1 = 7$ movimientos.

A continuación se muestra la secuencia animada del proceso solución paso a paso:

Detalle de los 7 movimientos:

1. Mover disco 1 (pequeño) de A $\rightarrow$ C
2. Mover disco 2 (mediano) de A $\rightarrow$ B
3. Mover disco 1 (pequeño) de C $\rightarrow$ B
4. Mover disco 3 (grande) de A $\rightarrow$ C
5. Mover disco 1 (pequeño) de B $\rightarrow$ A
6. Mover disco 2 (mediano) de B $\rightarrow$ C
7. Mover disco 1 (pequeño) de A $\rightarrow$ C

Curiosidad matemática: Para los 64 discos de la leyenda, los sacerdotes requerirían $2^{64} - 1 \approx 1.84 \times 10^{19}$ movimientos. Incluso a un ritmo de un movimiento por segundo sin fallos, tardarían aproximadamente 585.000 millones de años en terminar (¡varias veces la edad actual del Universo!).

Las Torres de Hanói también se pueden modelar mediante modelo de optimización binaria, ¿te atreves a intentar su modelización?

¿Quieres seguir explorando el mundo de la Investigación Operativa? Descubre más posts sobre el tema aquí.