Acertijos
Torre de Hanói
Tres postes, una pila de discos y una regla de duplicación debajo: el número mínimo de movimientos es 2ⁿ−1.
La leyenda dice que un templo en Benarés, India, contiene tres postes donde unos monjes mueven 64 discos de oro de un poste a otro, día y noche. El día que terminen, el mundo se acaba. ¿Da miedo? Una vez que veas cómo crece la cantidad de movimientos, sabrás qué tan lejos está realmente ese "fin del mundo".
Solo tres reglas
La meta: llevar toda una pila de discos del poste izquierdo al poste derecho.
- Mueve un disco a la vez, y solo el disco superior de un poste;
- Un disco solo puede colocarse sobre un poste;
- Un disco más grande nunca puede descansar sobre uno más pequeño.
Las reglas son simples, pero la tercera es una trampa: coloca un disco grande sobre uno pequeño y el intento se arruina en ese instante. Por cierto, el disco más pequeño es el más libre: puede descansar sobre cualquier cosa y nunca rompe una regla.
Resolver tres discos
Pensar en tres discos al mismo tiempo se enreda. El truco: domina dos discos, y tres discos siguen.
Para mover 3 discos al poste objetivo:
- Primero mueve los 2 discos superiores al poste libre del medio (3 movimientos);
- Mueve el disco más grande directamente al poste objetivo (1 movimiento);
- Mueve los 2 discos desde el poste libre de vuelta encima de él (3 movimientos).
movimientos, listo. ¿Notas algo? "Mover 2 discos" ocurrió dos veces: el trabajo grande se dividió en dos trabajos más pequeños más un movimiento propio.
Cuatro discos funcionan de la misma manera: mueve 3 discos al poste libre (7 movimientos), pasa el disco más grande (1 movimiento), mueve los 3 discos de vuelta encima (7 movimientos): 15 en total. Si puedes mover n−1 discos, puedes mover n. Este camino no tiene fin, y siempre funciona.
Cómo usar
Mueve un disco a la vez; nunca coloques un disco más grande sobre uno más pequeño
La cantidad de movimientos: 1, 3, 7, 15, 31…
Cuenta los movimientos mínimos:
| Discos | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| Movimientos mínimos | 1 | 3 | 7 | 15 | 31 |
El patrón es duplicar, luego sumar 1: , , … escrito como fórmula:
Para n discos, el mínimo es movimientos. Esto coincide exactamente con la estrategia: mover n discos = mover n−1 discos dos veces + mover el disco grande una vez.
Por qué 64 discos nunca terminan
Haz las cuentas
. Incluso a un disco por segundo, sin detenerse, los monjes necesitarían unos 585 mil millones de años, más de 40 veces la edad del universo (aproximadamente 14 mil millones de años). El mundo está a salvo.
Ese es el lado intimidante del crecimiento exponencial: agregar un disco es un paso pequeño, pero la cantidad de movimientos casi se duplica. Pasar de 5 discos a 10 eleva el mínimo de 31 a 1023; todavía son solo unos 17 minutos a un movimiento por segundo, sin problema; con 20 discos supera el millón de movimientos. Cualquier cosa que se duplica en cada paso muy pronto se vuelve inimaginable.
Ponte a prueba
Cuestionario rápido
1. ¿Cuál es el número mínimo de movimientos para 3 discos?
2. Al pasar de 3 discos a 4, el mínimo sube de 7 a ¿qué número?
3. ¿Por qué la leyenda de los 64 discos nunca se terminará?