La Tour d’Hanoï

Vive les casse-tête ! La Tour d’Hanoï, vous connaissez ? Les auteurs nous présentent ce jeu et s’intéressent à l’aspect mathématique de son fonctionnement reposant sur la numération binaire.

Michel Boutin & Frédéric de Ligt

© APMEP Juin 2020

⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅♦⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅

La Tour d’Hanoï¹ est un casse-tête inventé par le mathématicien français Édouard Lucas (1842-1891) qui en a fait don au Conservatoire national des arts et métiers de Paris ² en 1888. Ce casse-tête est constitué par une planchette sur laquelle on a fixé trois tiges ; sur l’une d’elles on a enfilé huit disques de diamètres décroissants, le plus petit en haut de la pile et le plus grand en bas.

Figure 1. Tour d’Hanoï sortie de sa boîte, et installée. © Musée
des arts et métiers, Cnam, Paris / Photo Michèle Favareille .

L’objectif du joueur est de transposer tous les disques d’une tige à une autre en respectant des règles de déplacement très précises : à chaque coup, le joueur prend un disque sur une tige et l’enfile sur une autre. Celle-ci pourra être soit vide, soit occupée par une pile d’un ou plusieurs disques. Dans ce cas, le joueur ne doit pas recouvrir un disque de diamètre inférieur à celui qu’il est en train de déplacer. Ainsi, un disque, quelle que soit sa grandeur, est toujours posé sur un plus grand que lui.

Un peu d’histoire

La Tour d’Hanoï est le seul jeu inventé par Édouard Lucas qui est entré dans la postérité. La première édition fut commercialisée en 1883 avec ce titre très curieux et apparemment très mystérieux : «La Tour d’Hanoï véritable casse-tête annamite. Jeu rapporté du Tonkin par le professeur N. Claus (de Siam). Mandarin du Collège Li-Sou-Stian !»

Figure 2. Boîte de la Tour d’Hanoï. (hauteur : 10 cm, largeur : 14,5 cm, longueur : 15 cm, masse : 365 g.) © Musée des arts et métiers, Cnam, Paris / Photo Michèle Favareille .

Le mystérieux professeur N. Claus (de Siam) fut rapidement identifié : il s’agit de Lucas d’Amiens³, professeur au lycée Saint-Louis.

Nombre de déplacements

Dans le fascicule n° 3 de la série «Jeux scientifiques», intitulé «La Tour d’Hanoï, jeu tombé de Saturne» paru en 1889 [2,3] sous le chapitre «L’exposant des puissances», Lucas donne une méthode simple pour calculer le nombre \(N\) de déplacements selon le nombre \(n\) d’étages : \(N=2^n-1\).

Figure 3. Page de titre du livret « Jeux scientifiques n° 3 » : La
Tour d’Hanoï.

Pour une tour de \(8\) étages, on a \(2^8 – 1 = 255\) déplacements. Pour une tour de \(64\) étages, on a un nombre de manœuvres égal à \(2^{64} – 1\), c’est un nombre de \(20\) chiffres. Cette valeur étant fastidieuse à calculer au XIXe siècle, Lucas donne un moyen pour connaître le nombre de chiffres du résultat : \(\text{E}\left(\log(2^{64})\right)+1\), où \(\text{E}(x)\) désigne la partie entière de \(x\). Dans le même fascicule, il justifie mathématiquement la formule proposée pour le nombre de déplacements de la Tour d’Hanoï comportant \(3\) tiges et \(n\) disques.

Quel que soit le nombre de disques, le plus grand d’entre eux n’est déplacé qu’une seule fois, mais le reste de la tour doit changer deux fois de tige, la première fois pour libérer le disque le plus bas et la seconde pour le recouvrir sur une autre tige. Ainsi, la totalité des déplacements, pour une tour de \(n\) disques est toujours égale à la somme de \(1\) déplacement (celui du grand disque) et de deux fois le nombre de déplacements correspondants à une tour de \(n – 1\) disques. Par exemple pour \(4\) disques, on a les trois plus petits à déplacer (\(7\) coups), puis le plus grand disque (\(1\) coup), puis une seconde fois les trois plus petits (\(7\) coups). On a donc \(N_4 = 7 + 1 + 7 = 15\) déplacements. Ainsi \(N_n = N_{n-1} + 1 + N_{n-1} = 1 + 2N_{n-1}\). Cette relation permet d’initier une suite récurrente dont la conclusion permettra d’établir une relation mathématique pour calculer directement le nombre de coups à effectuer pour déplacer \(n\) disques d’une tige à une autre : \(N_n = 2^n- 1\).

Codage binaire et ternaire des déplacements

Le déplacement des disques suit inéluctablement un protocole précis qui fut décrit dès 1884 par le petit-neveu d’Édouard Lucas, Raoul Olive : «Pour monter la tour sur trois tiges, quel que soit le nombre d’étages, il faut faire continuellement tourner le disque le plus petit, toujours dans le même sens de rotation circulaire tous les deux coups». En respectant ce protocole, la suite des déplacements peut être exprimée par une suite de nombres binaires dont le nombre de chiffres est égal au nombre de disques. La suite des nombres binaires qui correspond à celle des décimaux est appelée code binaire naturel.

Décimal		0	1	2	3	4	5	6	7
	\(2^0\)	0	1	0	1	0	1	0	1
	\(2^1\)	0	0	1	1	0	0	1	1
	\(2^2\)	0	0	0	0	1	1	1	1

Figure 4. Code décimal, code binaire naturel. Le binaire naturel est un code pondéré, par exemple : \(6 = 0(2^0) + 1(2^1) + 1(2^2)\).

Mais on peut organiser une suite de nombres binaires de plusieurs manières dont l’une d’elles, appelée code binaire réfléchi, est caractérisée par ses propriétés d’adjacence : quand on passe d’un nombre au suivant, un seul chiffre binaire change (\(0\) en \(1\) ou \(1\) en \(0\)). Cette propriété fut mise à profit en 1872 par un clerc de notaire lyonnais du nom de Louis Gros pour modéliser le fonctionnement du baguenaudier, un autre casse-tête beaucoup plus ancien. Près d’un siècle plus tard, en 1947, un ingénieur américain, Frank Gray, a utilisé ce même code dans un brevet d’invention où il décrit un système capable de transmettre des informations par impulsions électriques pour le compte de la société Bell Telephone Laboratories. Le code binaire réfléchi est connu depuis cette époque sous le nom de code de Gray [4] .

	\(\mathsf{d0}\)	0	1	1	0	0	1	1	0
	\(\mathsf{d1}\)	0	0	1	1	1	1	0	0
	\(\mathsf{d2}\)	0	0	0	0	1	1	1	1

Figure 5. Code binaire réfléchi (dit code de Gray).

Figure 6. Graphe montrant une propriété du code de Gray : un seul bit (binary digit) change d’état quand on passe d’un sommet à un des trois adjacents, par exemple : de 000 à un des trois sommets 001, 010 ou 100.

Le code de Gray a un intérêt dans de nombreux domaines y compris dans les jeux, en particulier pour modéliser les déplacements des disques de la Tour d’Hanoï. Les déplacements des disques correspondent à une succession de nombres binaires. Considérons une tour à trois disques (\(\mathsf{d0}\) pour le plus petit, \(\mathsf{d1}\) pour le moyen et \(\mathsf{d2}\) pour le plus grand), et trois tiges (\(\mathsf{A}\), \(\mathsf{B}\), \(\mathsf{C}\)).

Au départ, les disques sont sur la tige \(\mathsf{A}\). Sur la figure 7 on montre la succession des sept déplacements à partir de la situation codée \(000\). Le premier déplacement consiste à transposer le disque \(\mathsf{d0}\) de la tige \(\mathsf{A}\) vers la tige \(\mathsf{B}\). Cette nouvelle situation est alors codée \(001\). En effet, seul le disque \(\mathsf{d0}\) a changé de position. La succession des coups pour déplacer la tour d’une tige à une autre revient à écrire le code de Gray quel que soit le nombre de disques.

Le plus petit disque se déplace une fois sur deux, toujours dans le même sens, et les autres sont mis sur la seule tige disponible permettant de ne jamais recouvrir un disque plus petit. En partant de la tige \(\mathsf{A}\), pour un nombre impair de disques (\(3\) dans ce cas), si le cycle du petit disque est \(\mathsf{A}\)–\(\mathsf{B}\)–\(\mathsf{C}\)–\(\mathsf{A}\)–\(\mathsf{B}\) alors la position finale de la tour sera la tige \(\mathsf{B}\) ; en partant en sens inverse, \(\mathsf{A}\)–\(\mathsf{C}\)–\(\mathsf{B}\)–\(\mathsf{A}\)–\(\mathsf{C}\), la tour sera transposée en \(\mathsf{C}\). Pour un nombre pair de disques le scénario est inversé.

La plupart des nombreuses publications au sujet de la Tour d’Hanoï sont des approches mathématiques ; par exemple, les deux articles publiés dans la revue Pour la science, par Jean Lefort [5] en 2008, et Jean-Paul Delahaye [6] en 2015, modélisent les déplacements des disques par un graphe, ce qui permet d’indiquer clairement tous les déplacements possibles quelle que soit la phase de jeu. Ils soulignent aussi la correspondance entre la Tour d’Hanoï et les structures fractales. Par exemple, sur la figure 8, les trois graphes montrent les positions pour trois types de tour avec un disque (I), deux disques (II) ou trois disques (III). Pour trois disques, les sommets du triangle correspondent aux positions des disques de départ ou à l’arrivée : \(\mathsf{AAA}\) si les trois disques sont sur la tige \(\mathsf{A}\) ; \(\mathsf{BBB}\) s’ils sont sur la tige \(\mathsf{B}\) ; \(\mathsf{CCC}\), sur la tige \(\mathsf{C}\). Le caractère de droite du code à chacun des sommets indique toujours où se trouve le petit disque \(\mathsf{d0}\), le caractère central indique la position \(\mathsf{d1}\), et le caractère de gauche donne la position \(\mathsf{d2}\), c’est-à-dire du grand disque.

 

Quelques exemples de déplacements :

 

\(\mathsf{AAA}\), les trois disques sont sur la tige \(\mathsf{A}\) ;

 

\(\mathsf{AAA}\) vers \(\mathsf{AAB}\), \(\mathsf{d0}\) passe de la tige \(\mathsf{A}\) à la tige \(\mathsf{B}\) ;

 

\(\mathsf{AAB}\) vers \(\mathsf{ACB}\), \(\mathsf{d1}\) passe de la tige \(\mathsf{A}\) à la tige \(\mathsf{C}\) ;

 

\(\mathsf{ACB}\) vers \(\mathsf{ACC}\), \(\mathsf{d0}\) passe de la tige \(\mathsf{B}\) à la tige \(\mathsf{C}\).

 

Deux disques sont alors sur la tige \(\mathsf{C}\), etc. jusqu’à \(\mathsf{BBB}\).

 

Ces graphes indiquent toutes les possibilités pour déplacer la tour d’une tige à une autre. Les plus courts chemins suivent les côtés du triangle. En partant de la tige \(\mathsf{A}\) sur laquelle on a les trois disques \(\mathsf{AAA}\), si on part à gauche on arrive sur le sommet \(\mathsf{AAB}\) (c’est-à-dire que le petit disque est sur la tige \(\mathsf{B}\) et les autres restent sur la tige \(\mathsf{A}\)), si on part à droite on arrive sur le sommet \(\mathsf{AAC}\) (alors le petit disque est sur la tige \(\mathsf{C}\), et les autres sont restés sur la tige \(\mathsf{A}\)). En partant du sommet \(\mathsf{AAA}\) on peut aller en \(\mathsf{AAC}\), puis en \(\mathsf{AAB}\), etc.

Par exemple de \(\mathsf{AAA}\) en \(\mathsf{BBB}\), on peut suivre les sommets \(\mathsf{AAA}\)–\(\mathsf{AAC}\)–\(\mathsf{ABC}\)–\(\mathsf{ABB}\)–\(\mathsf{CBB}\)–\(\mathsf{CBC}\)–\(\mathsf{CAC}\)–\(\mathsf{CAA}\)–\(\mathsf{BAA}\)–\(\mathsf{BAC}\)–\(\mathsf{BBC}\)–\(\mathsf{BBB}\) ; les règles de déplacement sont respectées, mais le chemin suivi n’est pas le plus court. À partir de ces graphes, on voit la naissance d’une structure fractale qui se préciserait en augmentant le nombre de disques.

Références

1. Michel Boutin. « Les jeux dans les collections du Conservatoire national des arts et métiers de Paris, 4–La Tour d’Hanoï et le baguenaudier ». In : Le Vieux papier n° 431 (janvier 2019). Planches en couleur IX et X, pp. 25-26.↩
2. Michel Boutin. « Les jeux dans les collections du Conservatoire national des arts et métiers de Paris, 1–Le Jeu icosien (1859) ». In : Le Vieux papier n° 428 (avril 2018). Planche couleur I, pp. 433-441.↩
3. Édouard Lucas. La Tour d’Hanoï, jeu tombé de Saturne. Ce fascicule est le troisième numéro de la collection des « jeux scientifiques » qui en contient six ; tous édités à l’occasion de l’exposition universelle de 1889. Chambon & Baye et Édouard Lucas, Paris, 1889.↩
4. François Sauvageot. « Quadrature ». In : Au fil des maths n° 528 (avril-juin 2018), pp. 55-62.↩
5. Jean Lefort. « La tour de Hanoï, des jeux d’esprit pour la science ». In : Dossier pour la science no 59 (2008), pp. 91-93.
   ↩
6. Jean-Paul Delahaye. « Les tours de Hanoï, plus qu’un jeu d’enfants ». In : Pour la science n° 457 (novembre 2015), pp. 108-114.↩

⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅♦⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅

Michel Boutin est enseignant en génie électrique à la retraite.

Frédéric de Ligt enseigne les mathématiques au lycée Élie Vinet de Barbezieux.

---

1. Cette contribution est extraite d’un article paru dans la revue Le Vieux papier [1] .↩︎

2. .↩︎

3. Le lecteur averti d’aura reconnu l’anagramme de l’auteur.↩︎

---