Un jeu de disques inventé en 1883 par le mathématicien Édouard Lucas, où l'on apprend à penser par récurrence, à compter en binaire et à dessiner un triangle de Sierpiński — sans jamais quitter trois piquets de bois.
Le jeu en une phrase
On dispose de trois piquets A, B, C. Sur le piquet A sont enfilés n disques de tailles toutes différentes, du plus grand en bas au plus petit en haut : c'est la tour. Il s'agit de transporter toute la tour sur le piquet C.
Règle 1. On ne déplace qu'un seul disque à la fois.
Règle 2. On ne prend que le disque du dessus d'une pile.
Règle 3. Un disque ne se pose jamais sur un disque plus petit que lui.
Cinq disques transportés de A vers C en 31 coups — le plus petit nombre possible, comme on va le démontrer.
Lucas publia le jeu sous le pseudonyme de « professeur N. Claus (de Siam) », anagramme de Lucas d'Amiens, sa ville natale. La boîte racontait une légende : dans un temple de Bénarès, des prêtres déplaceraient jour et nuit soixante-quatre disques d'or, et le monde finirait avec le dernier coup. La cinquième planche fait le calcul.
1
Jouer : combien de coups faut-il ?
Touchez un piquet pour soulever son disque du dessus, puis un autre piquet pour l'y poser. Essayez d'abord avec trois disques, puis ajoutez-en : on sent vite que chaque disque supplémentaire double à peu près la longueur de la partie.
Touchez le piquet A pour prendre le petit disque.
Coups joués
0
Minimum théorique 2ⁿ − 1
7
Coups restants au mieux
7
Coups perdus
0
À retenir. « Coups restants au mieux » est recalculé à chaque instant par l'algorithme de la planche 2, depuis la position où vous êtes. « Coups perdus » = coups joués + coups restants − (2ⁿ − 1) : il reste à zéro tant que vous jouez parfaitement, et le bouton « Finir à ma place » ne perd jamais un coup. Avec 3 disques il en faut 7, avec 4 disques 15, avec 5 disques 31 : la suite 1, 3, 7, 15, 31… est celle des 2ⁿ − 1.
2
Penser par récurrence : le grand disque commande
Regardons le plus grand disque. Pour qu'il puisse quitter A et se poser sur C, il faut que tous les autres soient empilés sur B. D'où la stratégie en trois étapes, qui ramène le problème à n disques au même problème à n − 1 disques : c'est une récurrence.
① déplacer n−1 disques de A vers B · ② déplacer le grand disque de A vers C · ③ déplacer n−1 disques de B vers C
Si T(n) désigne le nombre de coups, on lit directement T(n) = 2T(n−1) + 1 avec T(1) = 1. En ajoutant 1 des deux côtés : T(n) + 1 = 2(T(n−1) + 1), la quantité T + 1 double à chaque disque, donc T(n) = 2ⁿ − 1. Et l'on ne peut pas faire mieux : le grand disque doit bouger au moins une fois, et avant comme après ce coup les n − 1 autres doivent former une tour complète ailleurs.
Le bandeau indique l'étape en cours de l'appel principal : orange ①, rouge ②, vert ③.
Nombre de déplacements de chaque disque (échelle logarithmique) ; les cadres pointillés marquent la valeur attendue 2ⁿ⁻ᵏ.
La pile des appels en cours
Chaque ligne est un sous-problème « déplacer k disques » en attente ; la ligne surlignée est celle qui joue le coup affiché. Il n'y a jamais plus de n lignes : c'est toute la mémoire dont l'algorithme a besoin.
Coups joués
0
T(n) par la récurrence
—
Formule 2ⁿ − 1
—
Disque k : 2ⁿ⁻ᵏ coups, somme
—
Ce que dit le tableau. Pour chaque n de 1 à 20, la page calcule T(n) par la récurrence, puis exécute réellement l'algorithme récursif en comptant les coups un par un (plus d'un million pour n = 20), et compare à 2ⁿ − 1 : —. Le diagramme des déplacements montre pourquoi : le plus petit disque bouge un coup sur deux, le suivant un coup sur quatre… et le plus grand une seule fois ; 2ⁿ⁻¹ + 2ⁿ⁻² + … + 1 = 2ⁿ − 1.
3
Compter en binaire : savoir quoi jouer sans rien retenir
La récurrence oblige à garder une pile d'appels. Il existe une façon de jouer qui ne demande aucune mémoire : le disque à déplacer au coup numéro m est donné par l'écriture de m en base 2. On compte le nombre de zéros à droite du dernier chiffre 1 : s'il y en a z, on déplace le disque numéro z + 1 (le plus petit porte le numéro 1).
La position affichée est calculée directement à partir de m, sans rejouer la partie ; la flèche rouge montre le coup numéro m.
La « règle graduée » : pour chaque coup de 1 à 2ⁿ − 1, une barre de hauteur égale au numéro du disque déplacé. Les graduations d'un double décimètre ont exactement ce dessin.
Disque déplacé au coup m
—
Trajet par la formule binaire
—
Contrôle formule / récurrence
—
Sens du petit disque
—
Trois règles de poche, toutes vérifiées. (1) Le disque déplacé au coup m est 1 + le nombre de zéros terminaux de m. (2) Il va du piquet (m ET (m−1)) mod 3 au piquet ((m OU (m−1)) + 1) mod 3 — opérations bit à bit, avec B et C échangés quand n est pair. (3) Le code de Gray g = m ⊕ ⌊m/2⌋ change d'un seul chiffre à chaque coup, celui du disque qui bouge (case rouge). La page a confronté ces règles à la récurrence pour n = 1 à 14, coup par coup et disque par disque. Pratique pour jouer à la main : le petit disque tourne toujours dans le même sens, un coup sur deux ; l'autre coup est le seul coup permis qui ne touche pas au petit disque.
4
Le graphe de tous les états : un triangle de Sierpiński
Chaque disque peut être sur l'un des trois piquets, et une fois chaque disque placé, l'ordre sur un piquet est forcé (le plus grand en bas). Il y a donc exactement 3ⁿ positions légales. Relions par un trait deux positions qui ne diffèrent que d'un coup : on obtient le graphe de Hanoï. Dessiné avec soin, il devient un triangle fait de trois triangles, faits chacun de trois triangles…
Couleur d'un point : piquet du plus grand disque (A bleu, B orange, C vert). Touchez un point pour voir la position ; le chemin rouge est le plus court vers le but (tour complète en C, coin en bas à droite).
La position choisie.
Sommets 3ⁿ
—
Arêtes comptées / 3(3ⁿ−1)/2
—
Diamètre (parcours en largeur)
—
Distance au but : graphe / algorithme
—
Longueur des arêtes dessinées
—
Contrôle sur toutes les positions
—
Pourquoi un triangle ? Le plus grand disque partage les positions en trois paquets de 3ⁿ⁻¹ (il est en A, en B ou en C) ; dans chaque paquet, les petits disques forment à leur tour un graphe de Hanoï à n − 1 disques. Les trois paquets ne se touchent que par un seul trait chacun : le coup du grand disque. En prenant tous les traits de longueur 1, le côté du grand triangle mesure 2ⁿ − 1 — c'est la solution optimale, qui longe le bord du bas. Aucune position n'est plus loin d'une autre que 2ⁿ − 1 coups (le diamètre, trouvé par un parcours en largeur depuis chaque sommet). Le même dessin apparaît dans le triangle de Pascal lorsqu'on colorie les nombres impairs.
5
Signature : la fin du monde, puis un quatrième piquet
La croissance en 2ⁿ est si brutale qu'elle transforme un jouet en horloge cosmique. Et la question change entièrement de nature dès qu'on ajoute un seul piquet : on ne sait plus écrire de formule simple, et la valeur exacte pour quatre piquets n'a été démontrée qu'en 2014.
Échelle des durées en puissances de dix (de 1 seconde à 10²² secondes). Le trait rouge marque la durée de la partie parfaite.
Coups nécessaires (calcul exact)
—
Durée de la partie
—
Comparée à l'âge de l'Univers
—
Contrôle 1 + 2 + … + 2ⁿ⁻¹
—
Le compte des prêtres. Pour 64 disques il faut 18 446 744 073 709 551 615 coups, nombre calculé ici en entiers exacts (un ordinateur ordinaire, qui travaille sur 53 chiffres binaires, ne peut même pas l'écrire sans l'arrondir). À un coup par seconde, cela fait environ 585 milliards d'années, une quarantaine de fois l'âge actuel de l'Univers (13,8 milliards d'années). Même un ordinateur jouant un milliard de coups par seconde y passerait près de six siècles. Une vie humaine de 80 ans, à un coup par seconde, ne suffit que pour 31 disques.
Avec quatre piquets A, B, C, D, on peut garer des disques sur deux piquets intermédiaires. En 1941, J. S. Frame et B. M. Stewart proposèrent la stratégie suivante : mettre de côté les k plus petits disques sur un piquet en utilisant les quatre piquets, transporter les n − k autres avec les trois piquets restants (2ⁿ⁻ᵏ − 1 coups), puis ramener les k premiers, en choisissant le meilleur k :
FS(n) = min1 ≤ k < n [ 2 FS(k) + 2ⁿ⁻ᵏ − 1 ]
Personne ne savait si l'on pouvait faire mieux. La page en a le cœur net pour les petites valeurs : elle explore toutes les positions (4ⁿ au total) par un parcours en largeur et trouve le vrai minimum.
Solution la plus courte trouvée par l'exploration complète.
Nombre de coups (échelle logarithmique) : trois piquets en bleu, Frame-Stewart en rouge, minimum exact trouvé par exploration en points verts.
Minimum exact (exploration)
—
Frame-Stewart
—
Avec trois piquets
—
Contrôle n = 1 à 8
—
Pour 20 disques : 3 piquets / 4 piquets
—
Une croissance d'une autre nature. Le quatrième piquet ne fait pas gagner quelques coups : il change la vitesse de croissance, qui n'est plus de l'ordre de 2ⁿ mais de √n · 2√(2n) — sur la figure, la courbe rouge s'aplatit pendant que la bleue file en ligne droite. L'exploration complète confirme Frame et Stewart pour n ≤ 8 ; la démonstration générale pour quatre piquets a été publiée par Thierry Bousch en 2014. Pour cinq piquets et plus, la question reste ouverte.
Repères historiques
1883Édouard Lucas, professeur au lycée Saint-Louis à Paris, met le jeu en vente sous le nom de « professeur N. Claus (de Siam) ».
1884Le journaliste Henri de Parville raconte la légende du temple de Bénarès et des soixante-quatre disques d'or dans la revue La Nature.
1941J. S. Frame et B. M. Stewart publient leur stratégie pour quatre piquets et plus, en réponse à un problème posé dans l'American Mathematical Monthly.
1944R. S. Scorer, P. M. Grundy et C. A. B. Smith étudient le graphe des positions et sa forme triangulaire.
1982Le neuropsychologue Tim Shallice crée la « tour de Londres », variante utilisée pour évaluer la planification chez les patients.
2014Thierry Bousch démontre que la stratégie de Frame-Stewart est optimale pour quatre piquets.
Synthèse
Une récurrence
Pour bouger le grand disque, il faut que les autres soient rangés ailleurs : T(n) = 2T(n−1) + 1, d'où 2ⁿ − 1 coups, et c'est un minimum.
Un compteur binaire
Le coup numéro m se lit dans l'écriture binaire de m ; la partie entière est un code de Gray qui défile. Aucune mémoire n'est nécessaire.
Une figure fractale
Les 3ⁿ positions forment un triangle de Sierpiński dont le côté est la solution optimale ; un piquet de plus suffit à rendre le problème difficile.
Pour aller plus loin
Démontrer l'optimalité à la main. Par récurrence sur n : dans toute solution, le grand disque bouge au moins une fois. Juste avant son premier départ, les n − 1 autres sont tous sur le troisième piquet (au moins T(n−1) coups pour les y mettre) ; juste après sa dernière arrivée en C, ils sont tous ailleurs et doivent rejoindre C (encore au moins T(n−1) coups). Total : au moins 2T(n−1) + 1.
D'une position quelconque. L'algorithme de « Finir à ma place » regarde le plus grand disque mal placé : s'il est déjà sur le bon piquet on l'oublie, sinon on range tous les plus petits sur le troisième piquet, on le déplace, puis on continue. La planche 4 vérifie qu'il donne exactement la distance du graphe pour toutes les positions.
Variantes. Tours cycliques (les disques ne tournent que dans un sens), tours à disques de deux couleurs à séparer, tours de Hanoï « à l'aveugle » où l'on part d'une position quelconque vers une autre position quelconque : le livre d'Andreas M. Hinz et de ses coauteurs, The Tower of Hanoi — Myths and Maths, en fait le tour.
Liens avec les autres pages. La règle graduée de la planche 3 est la même que celle du jeu de Nim binaire, et le triangle de Sierpiński rejoint le triangle de Pascal modulo 2.