La tour de Hanoï ordinaire a trois tiges. Que se passe-t-il si l’on en ajoute une, pour en avoir quatre ? Les règles sont les mêmes : on déplace un disque à la fois, sans jamais poser un grand disque sur un petit, pour amener la tour sur une autre tige.
Une tige de plus, et bien moins de coups
Il y a un endroit de plus où poser, donc écarter les disques est beaucoup plus facile. Si l’on compare les nombres minimaux de coups, l’écart grandit avec le nombre de disques.
| Nombre de disques | Avec 3 tiges | Avec 4 tiges |
|---|---|---|
| 3 disques | 7 coups | 5 coups |
| 4 disques | 15 coups | 9 coups |
| 5 disques | 31 coups | 13 coups |
| 6 disques | 63 coups | 17 coups |
| 7 disques | 127 coups | 25 coups |
| 8 disques | 255 coups | 33 coups |
| 10 disques | 1 023 coups | 49 coups |
| 64 disques | environ 18,4 trillions de coups | 18 433 coups |
Avec 3 tiges, déplacer 64 disques à un coup par seconde prend environ 584,5 milliards d’années (Combien d’années faut-il pour déplacer 64 disques ?). Avec 4 tiges, c’est 18 433 coups, soit environ 5 heures à un coup par seconde. Si les moines de la légende avaient ajouté une tige, le monde aurait fini le jour même.
Le « casse-tête du fromage » de Dudeney
C’est le créateur de casse-tête anglais Henry Dudeney qui a fait connaître largement la tour de Hanoï à quatre tiges. Dans son livre de 1907, The Canterbury Puzzles, il la pose sous le nom de « casse-tête de Reve » (Reve’s Puzzle). Un reeve (reve) était l’intendant d’un domaine.
Dans le problème de Dudeney, au lieu de disques, on déplace huit fromages de tailles différentes entre quatre tabourets. On ne doit pas poser un grand fromage sur un petit. La réponse est 33 coups, comme pour 8 disques dans le tableau ci-dessus.
La méthode de Frame-Stewart
Pour déplacer une tour avec quatre tiges en peu de coups, J. S. Frame et B. M. Stewart ont chacun publié la même idée en 1941. Pour déplacer une tour de n disques, on la divise en trois étapes :
- Déplacer les k disques du haut, en utilisant les quatre tiges, sur une tige autre que celle d’arrivée.
- Déplacer les n − k disques restants sur la tige d’arrivée, avec seulement trois tiges, sans toucher à la tige où se trouvent les k disques (2ⁿ⁻ᵏ − 1 coups).
- Déplacer sur la tige d’arrivée les k disques écartés à l’étape 1, en utilisant les quatre tiges.
Les étapes 1 et 3 sont de petites versions du même problème, donc on peut utiliser la récursivité (l’article sur l’algorithme). Il ne reste plus qu’à choisir combien de disques (k) laisser en haut pour obtenir le nombre de coups le plus petit. Avec 8 disques, le mieux est d’écarter d’abord les 4 ou 5 disques du haut, ce qui donne 33 coups.
Près de 100 ans sans preuve du « minimum »
On savait que la méthode de Frame-Stewart permet de déplacer la tour en peu de coups. Mais peut-on vraiment faire mieux ? Pendant longtemps, personne n’a su le démontrer.
Avec trois tiges, un seul fait suffit à démontrer tout de suite le nombre minimal de coups : « au moment de déplacer le plus grand disque, tous les autres doivent être rassemblés sur une seule tige » (la formule du nombre minimal de coups). Avec quatre tiges, au moment de déplacer le grand disque, les autres peuvent être répartis comme on veut sur les deux tiges restantes, et le nombre de suites de coups possibles explose.
Des ordinateurs ont examiné toutes les dispositions, et on a pu confirmer que cette méthode est minimale jusqu’à environ 30 disques. Puis, environ 100 ans après la question de Dudeney, en 2014, le mathématicien français Thierry Bousch a démontré que la méthode de Frame-Stewart est minimale quel que soit le nombre de disques. Pour cinq tiges ou plus, on considère que ce n’est toujours pas démontré.
À essayer soi-même
On peut fabriquer une tour de Hanoï à quatre tiges avec le carton de l’article sur la fabrication, en dessinant quatre ronds pour les emplacements. Voyez si vous pouvez déplacer 3 disques en 5 coups et 4 disques en 9 coups. On sent dans ses mains la différence avec trois tiges.
