Quand on résout la tour de Hanoï en un nombre minimal de coups, la suite des coups présente des régularités d’une beauté surprenante. Voici, l’une après l’autre, celles qu’on découvre dans la solution minimale (2ⁿ − 1 coups) qui déplace une tour de n disques de la gauche vers la droite. Les disques sont numérotés 1, 2, 3… du plus petit au plus grand.
Le nombre de déplacements de chaque disque est une puissance de 2
Dans la solution minimale, le nombre de déplacements de chaque disque est fixé. Avec n disques, le disque k bouge 2ⁿ⁻ᵏ fois.
| Disque (pour 4 disques) | Nombre de déplacements |
|---|---|
| 1 | 8 |
| 2 | 4 |
| 3 | 2 |
| 4 | 1 |
| Total | 15 |
Le plus grand disque bouge 1 fois, le suivant 2 fois, le suivant 4 fois… : à chaque disque plus petit, le nombre double. La somme est 1 + 2 + 4 + … + 2ⁿ⁻¹ = 2ⁿ − 1, ce qui correspond exactement au nombre minimal de coups.
On le comprend avec la même idée que la formule du nombre minimal de coups. Pour déplacer n disques, on déplace deux fois une tour de n − 1 disques. Les disques plus petits que le disque n bougent donc deux fois plus que quand on déplace n − 1 disques.
Quel disque bouge à quel coup
Dans la solution minimale à 4 disques, si l’on écrit, coup après coup, le numéro du disque qui bouge, on obtient ceci.
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
Le 1 apparaît un coup sur deux, entre eux le 2 un coup sur deux, et entre ceux-là le 3… C’est la même forme que la suite des longueurs des graduations d’une règle (courte, moyenne, courte, longue…).
On trouve cette suite tout de suite en écrivant le numéro du coup en binaire.
| Coup | Binaire | Nombre de 0 à la fin | Disque qui bouge |
|---|---|---|---|
| 1 | 1 | 0 | 1 |
| 2 | 10 | 1 | 2 |
| 3 | 11 | 0 | 1 |
| 4 | 100 | 2 | 3 |
| 5 | 101 | 0 | 1 |
| 6 | 110 | 1 | 2 |
| 7 | 111 | 0 | 1 |
| 8 | 1000 | 3 | 4 |
Au coup m, c’est le disque numéro « (nombre de 0 à la fin de m écrit en binaire) + 1 » qui bouge. Aux coups impairs, le binaire se termine par 1, donc c’est toujours le 1 qui bouge. C’est la raison de « aux coups impairs, on bouge le 1 » dans l’article sur la façon de résoudre le jeu.
De plus, les tiges de départ et d’arrivée s’obtiennent aussi par de simples calculs en binaire (l’article sur l’algorithme).
Le lien avec le code de Gray
Quand on compte en binaire à partir de 0, le nombre de chiffres qui changent à chaque pas varie (de 0111 à 1000, 4 chiffres changent). La façon d’écrire les nombres de sorte qu’un seul chiffre change à chaque pas s’appelle le « code de Gray ».
| Rang | Code de Gray | Chiffre qui change (en partant de la droite) |
|---|---|---|
| 0 | 000 | ― |
| 1 | 001 | 1 |
| 2 | 011 | 2 |
| 3 | 010 | 1 |
| 4 | 110 | 3 |
| 5 | 111 | 1 |
| 6 | 101 | 2 |
| 7 | 100 | 1 |
La suite des chiffres qui changent, « 1 2 1 3 1 2 1 », est exactement la même que celle des disques qui bougent dans la tour de Hanoï. Si l’on voit chaque disque comme un chiffre binaire, et « ce chiffre change » comme « ce disque bouge », alors la solution minimale de la tour de Hanoï revient à parcourir le code de Gray pas à pas.
Le sens de rotation des disques
Dans l’article sur la façon de résoudre le jeu, j’ai dit que le 1 tourne toujours dans le même sens. En fait, les autres disques suivent aussi une règle.
- Les disques impairs (1, 3, 5…) tournent tous dans le même sens que le 1.
- Les disques pairs (2, 4, 6…) tournent tous dans le sens inverse du 1.
Quand on déplace la tour de gauche à droite, avec un nombre impair de disques, le 1 va dans le sens « gauche → droite → milieu », et avec un nombre pair, dans le sens « gauche → milieu → droite ». Aucun disque ne change jamais de sens jusqu’à la fin.
Il y a aussi une autre règle, présentée dans résoudre 10 disques : dans la solution minimale, on ne pose jamais directement un disque impair sur un disque impair, ni un disque pair sur un disque pair.
Il y a 3ⁿ dispositions possibles
Combien y a-t-il de dispositions des disques qui respectent les règles ? Chaque disque peut être sur l’une des 3 tiges, et l’ordre des disques d’une même tige est imposé, du plus grand au plus petit : il y a donc 3ⁿ dispositions.
| Nombre de disques | Dispositions |
|---|---|
| 3 disques | 27 |
| 5 disques | 243 |
| 7 disques | 2 187 |
| 9 disques | 19 683 |
Et de n’importe quelle disposition, on peut toujours passer à n’importe quelle autre en respectant les règles. On sait aussi que si l’on représente chaque disposition par un point et qu’on relie par un trait les points qu’un coup permet de joindre, on obtient une figure très proche du « triangle de Sierpiński », où de petits triangles s’emboîtent dans un grand triangle.
Le mode « Puzzles » de l’app « Tour de Hanoï » crée ses problèmes parmi toutes ces dispositions. Même à ★5 avec 9 disques, les problèmes sont posés après avoir calculé le nombre minimal de coups pour chacune des 19 683 dispositions.
