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
| À comparer | Années |
|---|---|
| Déplacer 64 disques à un coup par seconde | Environ 584,5 milliards |
| Depuis la naissance de l’univers | Environ 13,8 milliards |
| Depuis la naissance de la Terre | Environ 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 disques | Nombre minimal de coups | À un coup par seconde |
|---|---|---|
| 7 disques | 127 coups | Environ 2 minutes |
| 10 disques | 1 023 coups | Environ 17 minutes |
| 15 disques | 32 767 coups | Environ 9 heures |
| 20 disques | 1 048 575 coups | Environ 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.
