Mover 3 discos es algo que logras después de unos pocos intentos. Pero cuando llegas a 5 o 7 discos, de repente tardas mucho más, y con 10 discos la cantidad de movimientos necesarios es casi imposible de contar a mano. ¿Por qué agregar un solo disco más lo vuelve todo tan difícil, tan de repente? La respuesta es que la torre de Hanói es un problema que crece de forma "exponencial".
Las reglas son sencillas. Hay tres postes, y los discos apilados por tamaño en el primer poste deben pasar todos al tercero. Solo hay dos condiciones: puedes mover un solo disco a la vez y nunca puedes poner un disco más grande sobre uno más pequeño. Con n discos, el número mínimo de movimientos necesarios es exactamente 2ⁿ − 1. Es decir, 1 movimiento con 1 disco, 3 con 2 discos, 7 con 3 discos, 15 con 4 discos… el número de movimientos casi se duplica cada vez que agregas un disco.
¿Por qué exactamente 2ⁿ−1? Para mover n discos, primero mueves los n−1 discos de arriba (todos menos el grande de abajo) al poste auxiliar, lo cual ya toma 2ⁿ⁻¹−1 movimientos; luego mueves el disco de abajo al poste destino (1 movimiento) y, por último, pasas los n−1 discos del poste auxiliar al poste destino (otros 2ⁿ⁻¹−1 movimientos). Escrito como ecuación: (2ⁿ⁻¹−1) + 1 + (2ⁿ⁻¹−1) = 2ⁿ−1. Esta forma de pensar, "dividir un problema grande en un problema más pequeño con exactamente la misma forma", se llama recursión. La torre de Hanói es el ejemplo más famoso para aprender a pensar de forma recursiva, y es un clásico cuando los estudiantes de informática empiezan a programar.
Hay una leyenda famosa sobre un templo de la India relacionada con este acertijo. Se dice que unos monjes están moviendo 64 discos de oro siguiendo esta misma regla, y que el mundo se acabará cuando terminen. El número mínimo de movimientos para 64 discos es 2⁶⁴−1: aun moviendo un disco por segundo sin parar, tardarían unos 585 mil millones de años, muchísimo más que la edad del propio universo (unos 13 800 millones de años). Gracias a esta leyenda, la torre de Hanói se cita a menudo como ejemplo clásico de lo aterradoramente rápido que pueden dispararse las cantidades que crecen de forma exponencial.
Este tipo de crecimiento exponencial importa mucho más allá de la torre de Hanói. Las bacterias que duplican su número a intervalos regulares, o una hoja de papel que se vuelve imposiblemente gruesa después de unos cuantos dobleces, funcionan con el mismo principio. Pocos ejemplos desarrollan tan bien la intuición de "una regla que parece pequeña, repetida, crece mucho más de lo que imaginas" como la torre de Hanói.
Si lo intentas con niños, empieza con 3 discos y pídeles que lo resuelvan con el mínimo de movimientos (7); luego sube a 4 discos (15) y a 5 discos (31), anotando cada vez "cuántos movimientos tomó". Ver por sí mismos que los movimientos necesarios crecen a un poco más del doble con cada disco extra hace que el concepto abstracto de crecimiento exponencial se entienda de forma mucho más vívida.
En nuestra página de actividad puedes elegir una dificultad de 3 a 6 discos y probarlo tú mismo, comparando en tiempo real tu número de movimientos con el mínimo teórico. Ponte el reto de resolverlo exactamente con el número mínimo de movimientos.