Avec n disques, le nombre minimal de coups pour déplacer la tour sur une autre tige est 2ⁿ − 1. C’est 2 multiplié par lui-même autant de fois qu’il y a de disques, moins 1.
| Nombre de disques | Nombre minimal de coups |
|---|---|
| 1 disque | 1 |
| 2 disques | 3 |
| 3 disques | 7 |
| 4 disques | 15 |
| 5 disques | 31 |
| 6 disques | 63 |
| 7 disques | 127 |
| 8 disques | 255 |
| 9 disques | 511 |
Chaque fois qu’on ajoute un disque, le nombre de coups double à peu près. Voyons pourquoi, pas à pas.
Regarder le plus grand disque
Considérons le déplacement d’une tour de n disques de la gauche vers la droite. Le plus grand disque est sous tous les autres, donc on ne peut pas le bouger tel quel. Pour le porter à droite, il faut qu’à cet instant on soit dans l’état suivant.
- Rien n’est posé sur le grand disque.
- La tige de droite est libre (on ne peut pas poser un disque plus petit sous le grand disque).
Autrement dit, les n − 1 autres disques doivent tous être empilés sur la tige centrale.
Diviser le nombre de coups en trois
À partir de là, on peut diviser la suite des coups pour déplacer n disques en trois étapes.
- Déplacer les n − 1 disques du haut de la gauche vers le milieu.
- Déplacer le plus grand disque de la gauche vers la droite, en un seul coup.
- Déplacer les n − 1 disques du milieu sur le grand disque.
Les étapes 1 et 3 sont toutes deux exactement le problème « déplacer une tour de n − 1 disques ». Si l’on note T(n) le nombre minimal de coups pour n disques, on a la relation
T(n) = T(n−1) + 1 + T(n−1) = 2 × T(n−1) + 1
Pour 1 disque, il faut 1 coup, donc T(1) = 1. On en tire ensuite 3, 7, 15, 31…
Pourquoi la formule est 2ⁿ − 1
Si l’on ajoute 1 aux deux côtés de cette relation, on obtient
T(n) + 1 = 2 × (T(n−1) + 1)
Cela veut dire que « le nombre de coups plus 1 » double exactement chaque fois qu’on ajoute un disque. Pour 1 disque, T(1) + 1 = 2, donc pour n disques, c’est 2 multiplié n fois par lui-même, soit 2ⁿ. En retirant 1, on a T(n) = 2ⁿ − 1.
Pourquoi on ne peut pas faire moins
On sait maintenant qu’on peut déplacer la tour en 2ⁿ − 1 coups avec la méthode ci-dessus. Mais n’existe-t-il pas une méthode qui en demande moins ?
Comme on l’a vu, au moment où l’on déplace le plus grand disque pour la première fois, les n − 1 autres disques doivent tous être empilés sur une même autre tige. Pour en arriver là, il faut au moins le nombre de coups nécessaire pour déplacer une tour de n − 1 disques. De même, après avoir posé le grand disque à droite pour la dernière fois, remettre les n − 1 autres disques dessus demande au moins le nombre de coups nécessaire pour déplacer une tour de n − 1 disques. Quant au grand disque lui-même, on le déplace au moins une fois.
Quelle que soit la méthode, ces trois nombres de coups sont toujours nécessaires. On ne peut donc pas faire moins que 2 × T(n−1) + 1 coups. On sait même que la solution en un nombre minimal de coups est unique.
127 coups dans le mode Classique de l’app
Le mode Classique de l’app « Tour de Hanoï » se joue à 7 disques, donc le nombre minimal de coups est 2⁷ − 1 = 127. Si le nombre de coups arrive à 127, c’est qu’on a résolu le puzzle en un nombre minimal de coups. Avec la façon de jouer présentée dans l’article sur les règles, en faisant tourner le petit disque toujours dans le même sens, on termine en exactement 127 coups.
