Para mover n discos primero debes apartar los n − 1 de arriba, luego mover el disco mayor una vez, y después volver a poner esos n − 1 encima. Así M(n) = 2M(n − 1) + 1 con M(1) = 1, que se resuelve como 2ⁿ − 1: ocho discos necesitan 255 movimientos y tres necesitan 7, en los dos primeros enlaces. 255 resultará familiar a quien lea tamaños de memoria: es el valor mayor que cabe en un byte sin signo, justo por esta razón.
La versión de Lucas venía con sesenta y cuatro discos de oro y una profecía de que el mundo acabaría cuando se hubiera movido la pila. A un movimiento por segundo eso son 2⁶⁴ − 1 = 1.844674407371⋅10+19 movimientos (tercer enlace), unos 585 mil millones de años, más de cuarenta veces la edad del universo, y el rompecabezas de ocho discos que tienes delante lleva un minuto y medio. La misma duplicación que hace trivial el caso pequeño vuelve geológico el grande, que es todo el sentido de una exponencial: 255 y 1.844674407371⋅10+19 son la misma regla a sesenta pasos de distancia.
Respuesta
255
Cómo leerla
2⁸ − 1 en el banco de trabajo. El segundo enlace son tres discos; el tercero es el conteo de sesenta y cuatro discos que acaba con el mundo.
Fuente
Édouard Lucas marketed the Tower of Hanoi in 1883 as the towers of Brahma at Benares; the minimum for n disks is 2ⁿ − 1, forced by the recurrence M(n) = 2M(n − 1) + 1
Resuélvelo en la calculadora
Estos enlaces abren la calculadora adecuada con los números de este problema ya escritos. La línea de arriba es lo que debería mostrar la pantalla: compruébalo tú mismo.