← Tous les textes du Grand Oral
MathsNSI
Trois tiges plantées dans une planchette, et sur la première une pile de disques de tailles décroissantes. Il faut transporter toute la pile sur une autre tige, en ne déplaçant qu'un disque à la fois et sans jamais poser un disque sur un plus petit. Le jeu, inventé en 1883 par le Français Édouard Lucas, se vend toujours dans les magasins de jouets, et il est devenu un exemple obligé des cours d'informatique.
Derrière ce casse-tête se cachent presque tous les chapitres de suites de terminale : une relation de récurrence, une suite arithmético-géométrique, une démonstration par récurrence, une suite géométrique et sa somme, des puissances de $2$ que le logarithme permet de dompter. On y trouve aussi la récursivité de la NSI, l'écriture binaire, du dénombrement et une figure fractale.
Ce texte rassemble ces connaissances. Il ne propose pas de Grand Oral tout fait : à chacun d'y choisir une direction et d'y construire sa question.
- Un jeu de 1883 et sa légende
- Jouer
- À la main : un, deux, trois disques
- La stratégie récursive et la suite $u_{n+1} = 2u_n + 1$
- On ne peut pas faire mieux
- La fin du monde : 585 milliards d'années
- La récursivité en Python
- Quel disque bouge ? L'écriture binaire
- Toutes les positions : un triangle de Sierpiński
- Variantes : quatre tiges, et la psychologie
- Des directions pour construire sa question
Édouard Lucas, né à Amiens en 1842, est professeur de mathématiques au lycée Saint-Louis puis au lycée Charlemagne, à Paris. Il est connu des spécialistes pour ses travaux sur les nombres premiers : en 1876, il démontre que $2^{127} - 1$, un nombre de $39$ chiffres, est premier. Ce sera le plus grand nombre premier connu pendant soixante-quinze ans. Il a aussi étudié les suites de type Fibonacci, dont l'une porte son nom.
Mais Lucas aime aussi les jeux, qu'il rassemble dans ses Récréations mathématiques. En 1883, il fait vendre un casse-tête sous un nom d'emprunt : « La Tour d'Hanoï, véritable casse-tête annamite », par le « professeur N. Claus (de Siam), mandarin du collège Li-Sou-Stian ». Il suffit de mélanger les lettres : N. Claus de Siam est l'anagramme de Lucas d'Amiens, et Li-Sou-Stian celle de Saint-Louis, son lycée. Le nom d'Hanoï n'est pas un hasard non plus : la France fait alors la conquête du Tonkin, et Hanoï est dans tous les journaux.
Le jeu de 1883 compte huit disques. La légende qui l'accompagne bientôt, racontée dès 1884 dans la revue La Nature, en compte beaucoup plus : dans un temple de Bénarès, des prêtres déplaceraient jour et nuit $64$ disques d'or selon les mêmes règles, et quand ils auraient fini, le temple s'écroulerait et le monde disparaîtrait. Cette légende est une invention de l'époque, sans aucune source indienne. On verra qu'elle n'a rien d'inquiétant, et c'est justement un calcul de puissances de $2$ qui le montre.
Avant tout calcul, il vaut la peine d'essayer. Touchez une tige pour prendre son disque du haut (il s'entoure de jaune), puis touchez la tige où le poser. Le but est de transporter toute la pile de la tige A sur la tige C. Le bouton « Solution » repart du début et montre la méthode optimale, coup par coup.
Avec trois disques, on s'en sort en tâtonnant. Avec cinq ou six, le tâtonnement ne suffit plus : il faut une méthode. C'est l'objet des sections suivantes.
Numérotons les disques du plus petit (disque $1$) au plus grand, et notons « A → C » le déplacement du disque du haut de la tige A vers la tige C. Appelons $u_n$ le plus petit nombre de coups qui permet de transporter $n$ disques d'une tige à une autre.
- Un disque : un seul coup, A → C. Donc $u_1 = 1$.
- Deux disques : le petit va sur B, le grand sur C, le petit sur C : A → B, A → C, B → C. Trois coups, et on ne peut pas faire moins puisqu'il faut bien déplacer le grand disque une fois et le petit au moins deux fois (il doit dégager le grand, puis le recouvrir). Donc $u_2 = 3$.
- Trois disques : voici une solution en sept coups.
| coup | déplacement | disque | A | B | C |
|---|---|---|---|---|---|
| début | 3 2 1 | ||||
| $1$ | A → C | $1$ | 3 2 | 1 | |
| $2$ | A → B | $2$ | 3 | 2 | 1 |
| $3$ | C → B | $1$ | 3 | 2 1 | |
| $4$ | A → C | $3$ | 2 1 | 3 | |
| $5$ | B → A | $1$ | 1 | 2 | 3 |
| $6$ | B → C | $2$ | 1 | 3 2 | |
| $7$ | A → C | $1$ | 3 2 1 |
Regardons ce tableau de près. Les coups $1$ à $3$ transportent les deux petits disques de A vers B : c'est exactement la solution à deux disques, avec B à la place de C. Le coup $4$ déplace le grand disque. Les coups $5$ à $7$ transportent les deux petits disques de B vers C : encore la solution à deux disques. Ainsi $7 = 3 + 1 + 3$. Cette observation est toute la clé du problème.
Pour transporter $n + 1$ disques de A vers C, on procède en trois temps :
- on transporte les $n$ plus petits disques de A vers B, en se servant de C comme tige auxiliaire (le grand disque, au fond de A, ne gêne pas : on peut tout poser dessus) ;
- on déplace le grand disque de A vers C, qui est libre ;
- on transporte les $n$ petits disques de B vers C, par-dessus le grand.
Les étapes 1 et 3 sont le même problème avec un disque de moins. Si l'on sait transporter $n$ disques en $u_n$ coups, on sait donc en transporter $n + 1$ en $u_n + 1 + u_n$ coups. On montrera dans la section suivante qu'on ne peut pas faire mieux ; admettons-le pour l'instant. La suite $(u_n)$ vérifie alors
$$u_1 = 1$$et, pour tout $n \geqslant 1$,
$$u_{n+1} = 2u_n + 1.$$On calcule de proche en proche : $u_2 = 3$, $u_3 = 7$, $u_4 = 15$, $u_5 = 31$, $u_6 = 63$, $u_7 = 127$, $u_8 = 255$. Chaque terme est une puissance de $2$ moins $1$, ce qui suggère $u_n = 2^n - 1$. Le jeu de Lucas à huit disques demande donc au moins $255$ coups.
La relation $u_{n+1} = 2u_n + 1$ est celle d'une suite arithmético-géométrique. La méthode du cours consiste à chercher le nombre $\ell$ tel que $\ell = 2\ell + 1$, soit $\ell = -1$, puis à étudier l'écart à ce nombre.
Étape 1. On pose $v_n = u_n + 1$. Pour tout $n \geqslant 1$,
$$\begin{aligned}v_{n+1} &= u_{n+1} + 1 \\ &= 2u_n + 1 + 1 \\ &= 2(u_n + 1) = 2v_n.\end{aligned}$$Étape 2. La suite $(v_n)$ est donc géométrique de raison $2$, de premier terme $v_1 = u_1 + 1 = 2$. Ainsi $v_n = 2 \times 2^{n-1} = 2^n$.
Étape 3. On en déduit $u_n = v_n - 1 = 2^n - 1$.
Initialisation. $u_1 = 1$ et $2^1 - 1 = 1$ : $\mathcal{P}(1)$ est vraie.
Hérédité. Soit $n \geqslant 1$ tel que $\mathcal{P}(n)$ soit vraie, c'est-à-dire $u_n = 2^n - 1$. Alors
$$\begin{aligned}u_{n+1} &= 2u_n + 1 \\ &= 2\left(2^n - 1\right) + 1 \\ &= 2^{n+1} - 2 + 1 \\ &= 2^{n+1} - 1,\end{aligned}$$donc $\mathcal{P}(n+1)$ est vraie.
Conclusion. Par récurrence, $u_n = 2^n - 1$ pour tout $n \geqslant 1$.
La suite $(u_n)$ est croissante et tend vers $+\infty$, et surtout elle double presque à chaque disque ajouté : un disque de plus, c'est deux fois plus de travail. C'est ce qu'on appelle une croissance exponentielle.
La stratégie récursive donne une solution en $2^n - 1$ coups. Mais un joueur astucieux ne pourrait-il pas trouver un raccourci ? Pour le savoir, il faut raisonner sur toutes les solutions possibles, pas seulement sur la nôtre. Notons $m_n$ le plus petit nombre de coups d'une solution quelconque pour $n$ disques. On sait déjà $m_n \leqslant 2^n - 1$, puisque notre méthode en est une.
Étape 1 : le grand disque doit bouger. Considérons une solution quelconque avec $n + 1$ disques, de A vers C. Le plus grand disque doit être déplacé au moins une fois. Regardons le premier moment où il bouge, disons de A vers une tige X. À cet instant, il est seul sur A (rien au-dessus de lui) et la tige X est vide (sinon il serait posé sur un plus petit). Les $n$ autres disques sont donc tous sur la troisième tige.
Étape 2 : avant ce premier déplacement. Au départ, les $n$ petits disques étaient sur A ; juste avant ce coup, ils sont tous sur une autre tige. Il a donc fallu transporter $n$ disques d'une tige à une autre : cela demande au moins $m_n$ coups.
Étape 3 : après le dernier déplacement. Regardons le dernier moment où le grand disque bouge : il arrive sur C, où il restera. Pour la même raison, les $n$ petits disques sont alors tous sur une même autre tige, et il faut ensuite les transporter sur C : au moins $m_n$ coups de plus.
Étape 4 : on compte. Les coups de l'étape 2, le déplacement du grand disque et les coups de l'étape 3 sont tous différents, donc toute solution compte au moins $m_n + 1 + m_n$ coups : $m_{n+1} \geqslant 2m_n + 1$. Comme notre méthode atteint $2m_n + 1$, on a $m_{n+1} = 2m_n + 1$.
Étape 5 : conclusion. La suite $(m_n)$ vérifie $m_1 = 1$ et la même relation que $(u_n)$ : les deux suites sont égales (récurrence immédiate), donc $m_n = 2^n - 1$.
Ce raisonnement est typique : pour montrer qu'un nombre est un minimum, il faut une construction qui l'atteint (une majoration) et un argument qui vaut pour toutes les solutions (une minoration). On peut même montrer un peu plus : la solution optimale est unique ; le grand disque n'y bouge qu'une fois.
Revenons aux prêtres de la légende et à leurs $64$ disques. Il leur faut au moins
$$\begin{aligned}u_{64} &= 2^{64} - 1 \\ &= 18\,446\,744\,073\,709\,551\,615.\end{aligned}$$À raison d'un coup par seconde, sans erreur ni pause, combien de temps cela prend-il ? Une année compte environ $365{,}25 \times 24 \times 3\,600 = 31\,557\,600$ secondes, donc la durée est d'environ
$$\frac{2^{64} - 1}{31\,557\,600} \approx 5{,}85 \times 10^{11} \ \text{années},$$soit environ $585$ milliards d'années. L'Univers a environ $13{,}8$ milliards d'années : il faudrait plus de $42$ fois son âge. Le monde ne risque rien.
Combien de chiffres a $2^{64}$ ? On écrit $2^{64} = 10^{x}$, et l'on prend le logarithme népérien des deux membres :
$$64\ln 2 = x \ln 10,$$donc
$$x = \frac{64 \ln 2}{\ln 10} \approx 19{,}27.$$Ainsi $2^{64} \approx 10^{19{,}27} \approx 1{,}8 \times 10^{19}$ : un nombre de $20$ chiffres, ce que confirme l'écriture complète ci-dessus.
Autre question naturelle : à partir de combien de disques la partie, à un coup par seconde, dure-t-elle plus d'un an ? On cherche le plus petit entier $n$ tel que $2^n - 1 > 31\,557\,600$, c'est-à-dire $2^n > 31\,557\,601$. La fonction $\ln$ étant strictement croissante, cela équivaut à
$$n \ln 2 > \ln(31\,557\,601),$$soit
$$n > \frac{\ln(31\,557\,601)}{\ln 2} \approx 24{,}9.$$Il faut donc $n = 25$ disques : $2^{25} - 1 = 33\,554\,431$ secondes, un peu plus d'un an. Avec $35$ disques, on dépasse le millier d'années ; avec $45$, le million. Chaque disque ajouté double la durée, et dix disques de plus la multiplient par $2^{10} = 1\,024$, environ mille.
La stratégie de la section 4 se traduit presque mot pour mot en un programme : pour transporter $n$ disques, on transporte $n - 1$ disques, on déplace le grand, on transporte encore $n - 1$ disques. Une fonction qui s'appelle elle-même s'appelle une fonction récursive ; elle doit avoir un cas de base (ici, zéro disque : il n'y a rien à faire) pour que les appels s'arrêtent.
La première partie affiche les sept coups du tableau de la section 3. La seconde ne fait que compter, avec exactement la relation $u_n = 2u_{n-1} + 1$ : le programme est la suite.
En NSI, la tour de Hanoï sert à montrer ce que fait l'ordinateur lors d'appels récursifs : chaque appel en attente est empilé dans la pile d'appels, et la profondeur de cette pile vaut ici $n + 1$. Elle montre aussi le prix de certains algorithmes : un algorithme qui fait $2^n$ opérations est inutilisable dès que $n$ dépasse quelques dizaines, quelle que soit la vitesse de l'ordinateur. Un ordinateur qui jouerait un milliard de coups par seconde mettrait encore près de six siècles pour les $64$ disques.
Dans le tableau à trois disques, la suite des disques déplacés est $1, 2, 1, 3, 1, 2, 1$. Avec quatre disques, on obtient $1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1$ : la suite précédente, le nouveau disque, puis encore la suite précédente, exactement comme dans la stratégie récursive.
Cette suite a une description surprenante. Écrivons le numéro $k$ du coup en base 2 : le disque déplacé au coup $k$ est $1 +$ le nombre de zéros à la fin de l'écriture binaire de $k$.
| coup $k$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ |
|---|---|---|---|---|---|---|---|---|
| en binaire | 1 | 10 | 11 | 100 | 101 | 110 | 111 | 1000 |
| disque | $1$ | $2$ | $1$ | $3$ | $1$ | $2$ | $1$ | $4$ |
En particulier, le petit disque bouge à tous les coups impairs, c'est-à-dire un coup sur deux, et l'on peut montrer qu'il tourne toujours dans le même sens autour des trois tiges. D'où une méthode pour jouer sans réfléchir : un coup sur deux, avancer le petit disque d'une tige dans son sens ; l'autre coup, faire le seul déplacement possible qui ne touche pas le petit disque.
Le disque $i$ bouge aux coups dont l'écriture binaire se termine par exactement $i - 1$ zéros. Dans la solution à $n$ disques, on vérifie (par exemple sur le tableau) que le disque $n$ bouge $1$ fois, le disque $n - 1$ bouge $2$ fois, le disque $n - 2$ bouge $4$ fois, et ainsi de suite : le disque $i$ bouge $2^{n-i}$ fois. Le nombre total de coups est donc la somme des termes d'une suite géométrique de raison $2$ :
$$\begin{aligned}1 + 2 + 4 + \cdots + 2^{n-1} &= \frac{2^n - 1}{2 - 1} \\ &= 2^n - 1.\end{aligned}$$On retrouve le résultat, par un tout autre chemin. Pour les $64$ disques, le petit disque à lui seul bouge $2^{63}$ fois, soit la moitié de tous les coups.
Quand on compte en binaire de $0$ à $7$, plusieurs chiffres changent parfois d'un coup (de 011 à 100, trois chiffres changent). Les ingénieurs utilisent une autre façon d'énumérer les nombres, le code de Gray (Frank Gray, 1947), où un seul chiffre change à chaque pas : 000, 001, 011, 010, 110, 111, 101, 100. Le chiffre qui change au pas $k$ obéit exactement à la même règle que le disque qui bouge au coup $k$ de la tour de Hanoï. Lucas avait d'ailleurs remarqué ce lien avec un autre casse-tête, le baguenaudier, qui suit le même code. Le code de Gray sert dans les capteurs de position (roues codeuses) et dans les télécommunications, parce qu'une erreur de lecture au moment d'un changement ne fausse qu'un seul chiffre.
Une position du jeu (autorisée par la règle) est entièrement décrite par la tige sur laquelle se trouve chaque disque : sur une tige donnée, l'ordre des disques est imposé, du plus grand en bas au plus petit en haut. Chacun des $n$ disques a $3$ tiges possibles, et ces choix sont indépendants : par le principe multiplicatif, il y a
$$3 \times 3 \times \cdots \times 3 = 3^n \ \text{positions}.$$Pour $3$ disques, cela fait $27$ positions ; pour $64$ disques, $3^{64} \approx 3{,}4 \times 10^{30}$. La solution optimale ne passe que par $2^n$ d'entre elles, une proportion $\left(\frac{2}{3}\right)^n$ qui tend vers $0$.
Dessinons chaque position par un point, et relions deux points quand on passe de l'une à l'autre en un seul coup. On obtient un graphe. Les positions où le grand disque est sur A forment un bloc, celles où il est sur B un autre, celles où il est sur C un troisième ; chaque bloc est une copie du graphe à $n - 1$ disques, et les trois blocs ne sont reliés que par un seul coup chacun (le grand disque qui change de tige). Cette structure, répétée à toutes les échelles, dessine le triangle de Sierpiński.
Le plus court chemin entre deux coins est un côté du grand triangle, qui traverse deux blocs et prend $2u_{n-1} + 1$ coups : on retrouve, sur un dessin, la relation de récurrence. Plus $n$ augmente, plus le graphe ressemble au triangle de Sierpiński, une figure étudiée dans le texte Le triangle de Sierpiński, où l'on retrouve aussi le triangle de Pascal.
En 1907, le Britannique Henry Dudeney pose dans un recueil d'énigmes la même question avec quatre tiges (le « problème de Reve »). Une tige de plus aide beaucoup : on peut mettre de côté une partie des petits disques et travailler avec les autres. En 1941, J. S. Frame et B. M. Stewart proposent une méthode, mais personne ne sait alors démontrer qu'elle est la meilleure possible. Pour quatre tiges, une preuve de son optimalité n'a été publiée qu'en 2014, par Thierry Bousch ; pour cinq tiges ou plus, la question reste ouverte. Un casse-tête d'enfant à trois tiges est donc devenu, avec une tige de plus, un vrai problème de recherche.
Parce qu'il demande de planifier plusieurs coups à l'avance et de garder en tête un but intermédiaire (« d'abord libérer le grand disque »), le jeu intéresse depuis les années 1970 les chercheurs en psychologie cognitive, qui étudient comment on résout un problème. En 1982, le neuropsychologue Tim Shallice en propose une version simplifiée, la tour de Londres (des boules de couleur sur trois tiges de hauteurs différentes), pour évaluer les capacités de planification de patients atteints de lésions du lobe frontal. Ces tests sont encore utilisés en neuropsychologie, avec des précautions d'interprétation : réussir ou rater une tour ne mesure pas à lui seul une « intelligence ».
Ce texte n'est pas un Grand Oral. Il rassemble des connaissances dans lesquelles chacun peut choisir une direction, la creuser et formuler sa propre question. Quelques directions possibles :
- Mathématiques : la modélisation d'un problème par une relation de récurrence ; la suite arithmético-géométrique et la démonstration par récurrence ; la différence entre trouver une solution et démontrer qu'elle est la meilleure ; la croissance exponentielle et le logarithme ; le dénombrement des positions et la somme géométrique.
- NSI : la récursivité, le cas de base et la pile d'appels ; le coût d'un algorithme exponentiel ; l'écriture binaire et le code de Gray ; le graphe des positions et la recherche d'un plus court chemin.
- Histoire : Édouard Lucas et les récréations mathématiques au XIXe siècle ; un jeu baptisé d'après l'actualité coloniale de 1883.
Le jury peut interroger sur les chapitres de spécialité mobilisés. Avec ce thème, il est utile de connaître parfaitement : les suites définies par récurrence ; les suites arithmétiques, géométriques et arithmético-géométriques ; la somme des termes d'une suite géométrique ; le raisonnement par récurrence ; la limite d'une suite géométrique ; la fonction logarithme népérien et la résolution d'inéquations du type $2^n > A$ ; le principe multiplicatif en dénombrement ; les fonctions en Python.
Pour réviser ces chapitres, l'application Maths FlashBac reprend tout le cours de spécialité en cartes.
- Tours de Hanoï, Édouard Lucas et code de Gray (Wikipédia).
- Sur ce site : Le triangle de Sierpiński, Le triangle de Pascal, Aristote et l'infini (sommes de suites géométriques) et La cryptographie (l'écriture binaire et l'exponentiation rapide).