On raconte cette légende à propos de la tour de Hanoï. Dans un temple en Inde se dresse une tour de 64 disques d’or, et des moines continuent de déplacer les disques en suivant les règles. Quand ils auront tout déplacé, le monde prendra fin…

Mais combien de temps faut-il vraiment pour déplacer 64 disques ?

Au minimum 2⁶⁴ − 1 coups

Avec n disques, le nombre minimal de coups est 2ⁿ − 1 (la raison est expliquée dans l’article sur le nombre minimal de coups). Pour 64 disques :

2⁶⁴ − 1 = 18 446 744 073 709 551 615 coups

C’est environ 18,4 trillions (18,4 milliards de milliards). Au Japon, on dirait environ 1845 kei, une unité qui vaut 10 000 000 000 000 000 : c’est 18,45 millions de fois 1 000 milliards.

À un coup par seconde

Supposons que les moines déplacent un disque par seconde, sans pause et sans jamais se tromper. En comptant une année d’environ 31,56 millions de secondes (365,25 jours), on obtient :

18 446 744 073 709 551 615 s ÷ 31 557 600 s ≈ 584,5 milliards d’années

À comparerAnnées
Déplacer 64 disques à un coup par secondeEnviron 584,5 milliards
Depuis la naissance de l’universEnviron 13,8 milliards
Depuis la naissance de la TerreEnviron 4,6 milliards

C’est à peu près 42 fois l’âge de l’univers. Même si la légende était vraie, nul besoin de s’inquiéter de la fin du monde.

Et avec un ordinateur ?

Imaginons que ce ne soit pas une main humaine, mais un ordinateur capable de calculer un milliard de coups par seconde. Il faudrait encore :

18 446 744 073 709 551 615 ÷ 1 000 000 000 ≈ 18,4 milliards de secondes ≈ environ 585 ans

Chaque coup est très simple à trouver, mais quand le nombre de disques augmente, le nombre de coups double à chaque fois. C’est un bon exemple de ce qu’on appelle une « croissance exponentielle ».

Jusqu’à combien de disques peut-on jouer à la main ?

À un coup par seconde, même en jouant le nombre minimal de coups, il faut :

Nombre de disquesNombre minimal de coupsÀ un coup par seconde
7 disques127 coupsEnviron 2 minutes
10 disques1 023 coupsEnviron 17 minutes
15 disques32 767 coupsEnviron 9 heures
20 disques1 048 575 coupsEnviron 12 jours

Pour jouer pendant une petite pause, 7 disques environ donnent la bonne durée. C’est pour cela que le mode Classique de l’app « Tour de Hanoï » se joue à 7 disques.