1. Une légende vendue avec un jeu
Paris, 1883.
En 1883 paraît à Paris un casse-tête signé « N. Claus de Siam, mandarin du collège Li-Sou-Stian ». Derrière ce nom se cache Édouard Lucas, professeur de mathématiques au lycée Saint-Louis : « N. Claus de Siam » est l'anagramme de « Lucas d'Amiens », sa ville natale, et « Li-Sou-Stian » celle de « Saint-Louis ».
Pour vendre son jeu, la tour de Hanoï, il l'accompagne d'une légende. Dans le grand temple de Bénarès, sous le dôme qui marque le centre du monde, \(64\) disques d'or auraient été empilés, à la création, sur l'une de trois aiguilles de diamant, du plus grand au plus petit. Jour et nuit, des prêtres les déplacent vers une autre aiguille. Quand la tour sera entièrement reconstruite, le temple tombera en poussière et le monde finira.
Les règles
On ne déplace qu'un disque à la fois, celui du dessus d'une pile.
On ne pose jamais un disque sur un disque plus petit.
But : faire passer toute la tour de l'aiguille A à l'aiguille C.
La légende est inventée ; le calcul qu'elle cache ne l'est pas. Combien de déplacements faut-il, au minimum, pour \(n\) disques ? On note \(h_n\) ce nombre.
2. À vous de jouer
Quelques disques d'abord, avant les 64 du temple.
Choisissez le nombre de disques. Cliquez sur une aiguille pour prendre le disque du dessus, puis sur une autre pour l'y poser. Le bouton « Montrer la solution » rejoue la solution la plus courte depuis le départ.
Déplacements : 0
Avec un disque, un seul déplacement suffit : \(h_1 = 1\). Avec deux disques : \(h_2 = 3\).
Avec \(4\) disques, la solution la plus courte compte \(15\) déplacements : c'est ce qu'affiche le compteur quand on lance la solution. On note \(h_{4} = 15\).
3. D'une tour à la suivante
Pour déplacer \(n+1\) disques, il faut savoir en déplacer \(n\).
Pour amener le plus grand disque sur l'aiguille C, il faut d'abord libérer celle-ci et dégager le dessus du grand disque : les \(n\) autres disques doivent être sur l'aiguille B. D'où trois phases.
La relation de récurrence
Pour tout entier \(n\geqslant 1\) : \[\begin{aligned} h_{n+1} &= h_n + 1 + h_n\\ &= 2\,h_n + 1, \end{aligned}\] avec \(h_1 = 1\). On ne peut pas faire moins : le grand disque doit bouger au moins une fois, et chaque fois qu'il bouge, les \(n\) autres sont tous sur la troisième aiguille.
Pour déplacer \(9\) disques : \(8\) disques vers l'aiguille du milieu (\(h_{8}\) déplacements), le grand disque (\(1\) déplacement), puis les \(8\) disques par-dessus (\(h_{8}\) déplacements) : \(h_{9} = 2\times 255 + 1 = 511\).
4. Ni arithmétique, ni géométrique
On double, puis on ajoute 1 : ni l'un, ni l'autre ?
Passer de \(h_n\) à \(h_{n+1}\), c'est multiplier par \(2\) puis ajouter \(1\). Ce n'est ni « ajouter toujours le même nombre », ni « multiplier toujours par le même nombre ».
\(h_2 - h_1 = 2\) et \(h_3 - h_2 = 4\) : les différences ne sont pas égales, \(h\) n'est pas arithmétique. \(\dfrac{h_2}{h_1} = 3\) et \(\dfrac{h_3}{h_2} = \dfrac{7}{3}\) : les quotients ne sont pas égaux, \(h\) n'est pas géométrique (voir l'exemple 3 du cours). Trois termes suffisent pour le prouver.
L'idée de Lucas : modifier un peu la suite pour la rendre géométrique, en ajoutant la même constante \(c\) à tous les termes.
\(\dfrac{5}{3} \neq \dfrac{9}{5}\) et \(5 - 3 \neq 9 - 5\) : avec \(c = 2\), la suite \(v\) n'est ni arithmétique, ni géométrique. L'écran suivant montre la bonne constante.
5. La bonne constante
Avec \(c = 1\), la suite devient géométrique.
On pose, pour tout \(n\geqslant 1\), \(v_n = h_n + 1\). Alors : \[\begin{aligned} v_{n+1} &= h_{n+1} + 1\\ &= 2\,h_n + 1 + 1\\ &= 2\,h_n + 2\\ &= 2\,(h_n + 1) = 2\,v_n. \end{aligned}\] La suite \(v\) est donc géométrique de raison \(2\), avec \(v_1 = h_1 + 1 = 2\).
Le nombre de déplacements
D'après le théorème 2 du cours : \(v_n = v_1\times 2^{\,n-1} = 2\times 2^{\,n-1} = 2^n\). Donc, pour tout \(n\geqslant 1\) : \[h_n = v_n - 1 = 2^n - 1.\]
Aide au calcul : quelques puissances de 2
\(2^8 = 256\) ; \(2^{10} = 1\,024\) ; \(2^{12} = 4\,096\) ; \(2^{16} = 65\,536\) ; \(2^{20} = 1\,048\,576\).
\(h_{10} = 2^{10} - 1 = 1\,024 - 1 = 1\,023\). Le piège \(1\,024\) oublie le « \(-1\) » : c'est \(v_{10}\), pas \(h_{10}\).
6. Les 64 disques : la console Python
\(2^{64}\) : hors de portée du calcul à la main.
Le programme ci-dessous calcule \(h_{64}\) avec la relation de récurrence, le contrôle avec la formule \(2^n - 1\), puis convertit le nombre de déplacements en années, à raison d'un déplacement par seconde.
Validez d'abord le programme sur un cas connu : remplacez 64 par 10 et
exécutez-le ; il doit redonner votre réponse à la question 5. Remettez ensuite 64.
Si la console ne se charge pas — réseau du lycée, tablette capricieuse —, le même programme s'exécute sur https://sciency.co/console.
Comment lire le résultat ?
Le programme affiche un nombre d'années entier. Groupez les chiffres par trois en partant de la droite : \(1\,000\,000\,000\) (un milliard) a dix chiffres, \(1\,000\,000\,000\,000\) (mille milliards) en a treize.
duree = h * 1 en conséquence : combien de temps leur faut-il pour les \(64\) disques ?Avec duree = h * 5, le programme affiche environ \(2\,923\) milliards d'années (un nombre à \(13\) chiffres). C'est bien plus que l'âge de l'Univers, environ \(13{,}8\) milliards d'années : la fin du monde de la légende n'est pas pour demain.
7. Une somme cachée
Le petit disque travaille plus que tous les autres.
Dans la solution la plus courte, le plus grand disque bouge une seule fois, le suivant deux fois, le suivant quatre fois… chaque disque bouge deux fois plus que celui qui est juste en dessous de lui. Avec \(4\) disques :
| disque | le plus grand | le 2e | le 3e | le plus petit | total |
|---|---|---|---|---|---|
| déplacements | \(1\) | \(2\) | \(4\) | \(8\) | \(15\) |
Avec \(n\) disques, le total est la somme des termes d'une suite géométrique de raison \(2\) : \[\begin{aligned} h_n &= 1 + 2 + 2^2 + \dots + 2^{\,n-1}\\ &= \dfrac{1 - 2^n}{1 - 2} = 2^n - 1 \end{aligned}\] d'après le théorème 5 du cours : on retrouve la formule de l'écran 5 par un autre chemin.
Pour \(64\) disques, \(2^{64} - 1\), c'est aussi le nombre de grains de blé de la légende de l'échiquier de Sessa : \(1 + 2 + 2^2 + \dots + 2^{63}\), un grain sur la première case, puis le double sur chaque case suivante.
8. Ce qu'il faut retenir
Le fil, d'un bout à l'autre.
Une suite ni arithmétique, ni géométrique…
Le nombre minimal de déplacements vérifie \(h_1 = 1\) et \(h_{n+1} = 2\,h_n + 1\) : la suite \(h\) n'est ni arithmétique, ni géométrique (trois termes suffisent à le prouver).
… mais la suite \(v\) définie par \(v_n = h_n + 1\) est géométrique de raison \(2\). On en déduit son terme général, puis celui de \(h\) : \(h_n = 2^n - 1\). On retrouve ce résultat avec la somme \(1 + 2 + \dots + 2^{\,n-1}\).
Une suite géométrique de raison \(2\) grandit si vite que \(64\) disques demandent des centaines de milliards d'années.
Votre parcours
Vous avez répondu juste à 0 question(s) sur 6.