Camino de la extinción según Hanói

Cuenta la leyenda que Dios al crear el mundo, colocó tres varillas de diamante con 64 discos en la primera. También creó un monasterio con monjes, los cuales tienen la tarea de resolver esta Torre de Hanói divina. El día que estos monjes consigan terminar el juego, el mundo acabará.

El juego consiste en pasar todos los discos a la tercera varilla colocados de mayor a menor ascendentemente.
Las reglas son:

-Sólo se puede mover un disco cada vez.

-Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.

-Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.

Actualmente los monjes siguen intentándolo y cuando acaben todos sufriremos desgracias inimaginables, pero ¿cuándo ocurrirá eso?

De momento el mejor algoritmo que se ha conseguido encontrar para resolver el juego tiene una complejidad temporal exponencial.

La complejidad temporal, para los que no sepan lo que es, es el tiempo que tarda un algoritmo en ejecutarse independientemente del tipo de máquina en el que se ejecute.

El tiempo en la complejidad temporal no se mide en segundos, se define una unidad de medida teórica para evitar utilizar los segundos. Esta se puede medir como el número de pasos (movimientos) que realiza un algoritmo para una entrada dada.

Una complejidad exponencial es aquella que crece exponencialmente conforme aumenta el tamaño del problema.

Concretamente el juego tiene una complejidad 2ⁿ donde n es el número de discos, por lo tanto el juego terminará después de ejecutar 2⁶⁴ movimientos (pasos) de los discos.

Supongamos que un monje puede hacer un movimiento por segundo y que los monjes se van turnando para cambiar los discos de manera que en ningún momento del día se para de cambiar discos.

Los monjes tardarán en hacer el trabajo

2⁶⁴ = 18446744073709600000 segundos

que a su vez son:

307445734561826000 minutos

5124095576030430 horas

213503982334601 días

584942417355 años.

Suponiendo que el mundo tiene aproximadamente 4 millones y medio de años y ese es el tiempo que llevan los monjes trabajando, sabemos aproximadamente cuando será la fecha de nuestra extinción. Así que no hagáis planes para dentro de 584937917355 años (584.938 millones de años) que será la fecha de la extinción y ese día es para estar en familia (como en Navidad).

Puedes obtener mas información sobre el juego aquí.