Pour déplacer n disques il faut d'abord écarter les n − 1 du dessus, puis déplacer le plus grand disque une fois, et ensuite remettre ces n − 1 dessus. Ainsi M(n) = 2M(n − 1) + 1 avec M(1) = 1, qui se résout en 2ⁿ − 1 : huit disques ont besoin de 255 mouvements et trois ont besoin de 7, dans les deux premiers liens. 255 paraîtra familier à qui lit des tailles de mémoire : c'est la plus grande valeur qui tient dans un octet non signé, exactement pour cette raison.
La version de Lucas venait avec soixante-quatre disques d'or et une prophétie selon laquelle le monde finirait quand la pile aurait été déplacée. À un mouvement par seconde cela fait 2⁶⁴ − 1 = 1.844674407371⋅10+19 mouvements (troisième lien), environ 585 milliards d'années, plus de quarante fois l'âge de l'univers, et le casse-tête à huit disques que vous avez devant vous prend une minute et demie. Le même doublement qui rend trivial le petit cas rend géologique le grand, ce qui est tout le sens d'une exponentielle : 255 et 1.844674407371⋅10+19 sont la même règle à soixante pas de distance.
Réponse
255
Comment la lire
2⁸ − 1 dans l'espace de travail. Le deuxième lien est trois disques ; le troisième est le compte des soixante-quatre disques qui met fin au monde.
Source
É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
Résolvez-le dans la calculatrice
Ces liens ouvrent la calculatrice appropriée avec les nombres de ce problème déjà saisis. La ligne ci-dessus correspond à ce que l'écran devrait afficher : vérifiez par vous-même.