Torres de Hanoi y crecimiento exponencial

🗼 El problema

El juego de las Torres de Hanoi consiste en mover una pila de discos desde un poste inicial a otro, con las siguientes reglas:

Solo se puede mover un disco a la vez.
No se puede colocar un disco grande sobre uno más pequeño.
Solo se puede mover el disco que esté arriba de una torre.

Dado un número $n$ de discos, ¿cuál es la secuencia mínima de movimientos necesarios para resolver el problema?

🔁 Solución recursiva

La idea recursiva es:

Mover los $n - 1$ discos superiores a un poste auxiliar.
Mover el disco más grande al destino.
Mover los $n - 1$ discos del auxiliar al destino.

Este procedimiento se repite para cada subconjunto de discos.


def hanoi(n, origen, destino, auxiliar):
    if n == 1:
        print(f"Mover disco 1 de {origen} a {destino}")
    else:
        hanoi(n - 1, origen, auxiliar, destino)
        print(f"Mover disco {n} de {origen} a {destino}")
        hanoi(n - 1, auxiliar, destino, origen)
 
# Ejecutar para 3 discos
hanoi(3, 'A', 'C', 'B')

📈 Sucesión asociada

Llamemos $T_n$ al número mínimo de movimientos necesarios para resolver el problema con $n$ discos. A partir del algoritmo recursivo, podemos deducir la siguiente relación:

T_1 = 1,\quad T_n = 2T_{n-1} + 1

Desarrollando los primeros términos:

T_2 = 2T_1 + 1 = 3 \\ T_3 = 2T_2 + 1 = 7 \\ T_4 = 2T_3 + 1 = 15 \\ T_5 = 2T_4 + 1 = 31

Se puede inducir que la fórmula cerrada es:

T_n = 2^n - 1

Este crecimiento es exponencial: al aumentar $n$ , el número de pasos se duplica y se suma uno.

📊 Visualización del crecimiento


import matplotlib.pyplot as plt
 
def movimientos(n):
    return 2**n - 1
 
n_vals = list(range(1, 21))
t_vals = [movimientos(n) for n in n_vals]
 
plt.plot(n_vals, t_vals, marker='o')
plt.title("Número de movimientos en Torres de Hanoi")
plt.xlabel("n (número de discos)")
plt.ylabel("T(n) = 2ⁿ - 1")
plt.yscale('log')  # opcional: para ver el crecimiento exponencial como línea recta
plt.grid(True)
plt.show()

💡 Conclusiones

Las Torres de Hanoi son un ejemplo clásico de cómo la recursión resuelve un problema estructurado.
El número de pasos forma una sucesión recursiva con fórmula cerrada: $T_n = 2^n - 1$ .
Este tipo de crecimiento aparece en muchos algoritmos y estructuras de datos.