Les tours de Hanoï I : le problème classique

Piste verte 21 juin 2016  - Ecrit par  Jonathan Chappelon Voir les commentaires (5)

« La poste nous a remis récemment une petite boîte en carton peint, sur laquelle on lit : la Tour d’Hanoï, véritable casse-tête annamite, rapporté du Tonkin par le professeur N. Claus (de Siam), mandarin du collège Li-Sou-Stian. Un vrai casse-tête, en effet, mais intéressant. Nous ne saurions mieux remercier le mandarin de son aimable intention à l’égard d’un profane qu’en signalant la Tour d’Hanoï aux personnes patientes possédées par le démon du jeu. » [1]

Le problème des tours de Hanoï a été inventé par le mathématicien français Édouard Lucas (1842-1891). Il est introduit de la manière suivante dans le tome 3 de son livre « Récréations mathématiques », qui a été publié à titre posthume en 1893 [2].

Un de nos amis, le professeur N. Claus (de Siam), mandarin du collège Li-Sou-Stian, a publié à la fin de l’année dernière, un jeu inédit qu’il a appelé la Tour d’Hanoï, véritable casse-tête annamite qu’il n’a pas rapporté du Tonkin, quoiqu’en dise le prospectus. Cette tour se compose d’étages superposés et décroissants, en nombre variable, représentés par huit pions en bois percés à leur centre, et enfilés dans l’un des trois clous fixés sur une tablette. Le jeu consiste à déplacer la tour en enfilant les pions sur un des deux autres clous et en ne déplaçant qu’un seul étage à la fois, mais en défense expresse de poser un étage sur un autre plus petit.

$\ $

$\ $

Lucas annonce donc que ce problème est dû à l’un de ses amis N. Claus (de Siam), mandarin du collège Li-Sou-Stian. On peut remarquer que « N. Claus (de Siam) » est l’anagramme de « Lucas d’Amiens », Amiens étant la ville natale d’Édouard Lucas, et « Li-sou-Stian » est celui de « Saint Louis », nom du lycée parisien où Lucas enseigne de 1879 à 1890. Après quelques observations sur ce problème, auxquelles nous nous intéresserons ensuite, il continue avec l’histoire, ou plutôt le mythe suivant.

LES BRAHMES TOMBENT !

Le mandarin N. Claus (de Siam) nous raconte qu’il a vu, dans ses voyages pour la publication des écrits de l’illustre Fer-Fer Tam-Tam, dans le grand temple de Bénarès, au-dessous du dôme qui marque le centre du monde, trois aiguilles de diamant, plantée dans une dalle d’airain, hautes d’une coudée et grosses comme le corps d’une abeille. Sur une de ces aiguilles Dieu enfila, au commencement des siècles, soixante-quatre disques d’or pur, le plus large reposant sur l’airain, et les autres, de plus en plus étroits, superposés jusqu’au sommet. C’est la tour sacrée de Brahma. Nuit et jour, les prêtres se succèdent sur les marches de l’autel, occupés à transporter la tour de la première aiguille de diamant sur la troisième, sans s’écarter des règles fixes que nous venons d’indiquer, et qui ont été imposées par Brahma. Quand tout sera fini, la tour et les brahmes tomberont, et ce sera la fin des mondes !

Le problème classique

Reformulons maintenant ce problème de manière plus précise. Considérons trois piquets, notés $A$, $B$ et $C$, et un nombre fini de disques de tailles différentes que l’on suppose placés initialement par taille décroissante sur le piquet $A$. Le but est ici de transférer cette tour de disques du piquet $A$ au piquet $C$ en respectant les règles suivantes :

  • un seul disque peut être déplacé à la fois,
  • un disque ne peut être placé sur un disque de taille plus petite.

Par exemple, pour trois disques, on peut déplacer la tour du piquet $A$ au piquet $C$ en effectuant $7$ mouvements comme illustré ci-dessous.

Nombre minimal de mouvements

Nous allons ici déterminer le nombre minimal de mouvements $\mathrm{T}(n)$ pour déplacer une tour de $n$ disques du piquet $A$ au piquet $C$.

Pour $n=0$, on peut supposer que $\mathrm{T}(0)=0$ et pour un unique disque, il est évident que $\mathrm{T}(1)=1$.

Pour deux disques, il faut déplacer le grand disque du piquet $A$ au piquet $C$ et donc pour ce faire le petit disque doit être positionné sur le piquet intermédiaire $B$. Les trois mouvements suivants sont donc nécessaires et suffisants : le petit disque de $A$ vers $B$, le grand disque de $A$ vers $C$ et enfin le petit disque de $B$ vers $C$. On obtient donc $\mathrm{T}(2)=3$.

Par l’exemple proposé à la figure précédente, on sait que l’on peut déplacer la tour de trois disques en effectuant $7$ mouvements et donc $\mathrm{T}(3)\leqslant 7$. Montrons que l’on ne peut pas faire avec moins de mouvements :

  • Pour déplacer le plus grand disque du piquet $A$ vers un second piquet, $B$ ou $C$, il faut préalablement déplacer les deux plus petits disques du piquet $A$ vers le troisième piquet, $C$ ou $B$ respectivement. Ce déplacement des deux plus petits disques nécessite au moins $\mathrm{T}(2)=3$ mouvements.
  • Le plus grand disque est déplacé au moins une fois.
  • Pour le déplacement final du plus grand disque vers le piquet $C$ à partir d’un second piquet, $A$ ou $B$, il faut préalablement que les deux plus petits disques soient positionnés sur le troisième piquet, $B$ ou $A$ respectivement. Après le déplacement final du plus grand disque, les deux plus petits disques sont alors déplacés du piquet $A$ ou $B$ vers le piquet $C$ et ce déplacement nécessite au moins $\mathrm{T}(2)=3$ mouvements.

Au total, nous venons de montrer que pour déplacer les trois disques $2\mathrm{T}(2)+1=7$ mouvements sont nécessaires et donc $\mathrm{T}(3)\geqslant 7$.

Ce résultat peut être généralisé pour tout $n\geqslant 2$.

\[ \mathrm{T}(n) = 2\mathrm{T}(n-1)+1 \text{ pour tout } n\geqslant 1. \]

Preuve

Soit $\ n\geqslant 1$. Pour montrer que $\ \mathrm{T}(n) \leqslant 2\mathrm{T}(n-1)+1$, il suffit de proposer une solution utilisant ce nombre de mouvements. Considérons la solution suivante :

  • les $\ n-1$ plus petits disques sont transférés du piquet $A$ vers le piquet intermédiaire $B$ en $\ \mathrm{T}(n-1)$ mouvements, le nombre minimal de mouvements pour déplacer $\ n-1$ disques d’un piquet à un autre,
  • le plus grand disque est déplacé du piquet $A$ au piquet $C$ en $1$ mouvement,
  • les $\ n-1$ plus petits disques sont transférés du piquet $B$ vers le piquet $C$ en $\ \mathrm{T}(n-1)$ mouvements.

Remarquons que cette solution pour $\ n=3$ correspond à celle de l’exemple précédent.

Montrons maintenant que $\ \mathrm{T}(n) \geqslant 2\mathrm{T}(n-1)+1$. La preuve est similaire à ce qui a été fait pour $\ n=3$.

  • Pour déplacer le plus grand disque du piquet $A$ vers un second piquet, $B$ ou $C$, il faut préalablement déplacer les $\ n-1$ plus petits disques du piquet $A$ vers le troisième piquet, $C$ ou $B$ respectivement. Ce déplacement des $\ n-1$ plus petits disques nécessite au moins $\ \mathrm{T}(n-1)$ mouvements.
  • Le plus grand disque est déplacé au moins une fois.
  • Pour le déplacement final du plus grand disque vers le piquet $C$ à partir d’un second piquet, $A$ ou $B$, il faut préalablement que les $\ n-1$ plus petits disques soient positionnées sur le troisième piquet, $B$ ou $A$ respectivement. Après le déplacement final du plus grand disque, les $\ n-1$ plus petits disques sont déplacés du piquet $A$ ou $B$ vers le piquet $C$ et ce déplacement nécessite au moins $\ \mathrm{T}(n-1)$ mouvements.

Au total, nous venons de montrer que pour déplacer les $\ n$ disques $\ 2\mathrm{T}(n-1)+1$ mouvements sont nécessaires.

Cette preuve met donc en lumière la solution optimale du problème pour $n\geqslant 1$ disques, définie de manière récursive en fonction de la solution optimale pour $n-1$ disques.

Pour déplacer les $n$ disques du piquet $A$ vers le piquet $C$ en utilisant $\mathrm{T}(n)$ mouvements, on procède de la manière suivante :

  • les $n-1$ plus petits disques sont transférés du piquet $A$ vers le piquet $B$ en $\mathrm{T}(n-1)$ mouvements,
  • le plus grand disque est déplacé du piquet $A$ au piquet $C$ en $1$ mouvement,
  • les $n-1$ plus petits disques sont transférés du piquet $B$ vers le piquet $C$ en $\mathrm{T}(n-1)$ mouvements.

La formule ainsi obtenue nous permet de calculer $\mathrm{T}(n)$ pour toute valeur de $n$ mais pour $n$ très grand, cela prend beaucoup de temps. Heureusement, il est possible de donner une formule explicite de $\mathrm{T}(n)$ en fonction de $n$.

\[ \mathrm{T}(n) = 2^n-1 \text{ pour tout } n\geqslant 0. \]

Preuve

Pour $n=0$, on a $\mathrm{T}(0)=0=1-1=2^0-1$. Pour $n\geqslant 1$, on sait que $\mathrm{T}(n)=2\mathrm{T}(n-1)+1$ et donc
\[ \mathrm{T}(n)+1 = 2\mathrm{T}(n-1)+2 = 2\left(\mathrm{T}(n-1)+1\right). \]
Ainsi,
\[ \mathrm{T}(n)+1 = 2\left(\mathrm{T}(n-1)+1\right) = 2\times 2\left(\mathrm{T}(n-2)+1\right) = \cdots = \underbrace{2\times\cdots\times 2}_{n\text{ fois}}\underbrace{\left(\mathrm{T}(0)+1\right)}_{=1}, \]
ce qui implique que $\mathrm{T}(n)=2^n-1$.

Temps de résolution

Ainsi, si l’on suppose que le déplacement d’un disque est réalisé en une seconde, on peut résoudre le problème des tours de Hanoï à $n$ disques en $2^n-1$ secondes.

La tour de huit disques, représentée sur le croquis, peut être déplacée en $2^8-1=255$ secondes, soit $4$ minutes et $15$ secondes.

La tour de $64$ disques, dont il est question dans l’histoire « Les Brahmes tombent ! » de Lucas, nécessitent
\[ 2^{64}-1 = 18\ 446\ 744\ 073\ 709\ 551\ 615 \]
secondes soit plus de $584\ 554\ 531\ 243$ années.

Ce nombre gigantesque $2^{64}-1$ se retrouve également dans d’autres histoires. Par exemple, dans son texte, Lucas cite le jeu du baguenaudier ou encore la prétendue récompense faite à l’inventeur du jeu d’échecs.

Le nombre prodigieux que nous venons d’écrire se retrouve encore dans la théorie du baguenaudier de soixante-quatre anneaux. Ce nombre était connu des Indiens ; l’écrivain Asaphad rapporte, en effet, que Sessa, fils de Daher, imagina le jeu des échecs, où le roi, quoique la pièce la plus importante, ne peut faire un pas sans le secours de ses sujets, les pions, dans le but de rappeler au monarque indien Scheran les principes de justice et d’équité avec lesquels il devait gouverner. Scheran, enchanté d’une leçon donnée d’une manière si ingénieuse, promit à l’inventeur de lui donner tout ce qu’il voudrait pour sa récompense. Celui-ci répondit : « Que Votre Majesté daigne me donner un grain de blé pour la première case de l’échiquier, deux pour la seconde, quatre pour la troisième, et ainsi de suite en doublant jusqu’à la soixante-quatrième case. » Il aurait fallu huit fois la superficie de la Terre, supposée entièrement ensemencée, pour avoir en une année de quoi satisfaire au désir du modeste bramine. Le nombre de grains de blé est égal au nombre de déplacements de la tour d’Hanoï à soixante-quatre étages.

Une version simplifiée de la solution optimale.

La solution optimale présentée précédemment est définie de manière récursive. Nous allons ici simplifier sa définition.

Remarquons tout d’abord que dans la solution optimale, un mouvement sur deux concerne le plus petit disque. Ce résultat est facile à vérifier sur l’exemple précédent pour trois disques. Montrons-le de manière générale pour $n\geqslant 1$ disques :

  • Si deux mouvements consécutifs concernent le plus petit disque, alors il est possible de remplacer ces deux mouvements par un seul. Si le plus petit disque est déplacé du piquet $X$ vers $Y$ et ensuite déplacé du piquet $Y$ vers $Z$, alors on considère directement le déplacement de ce disque du piquet $X$ vers le piquet $Z$. On réduit ainsi le nombre de mouvements total de un, ce qui contredit l’optimalité de la solution de départ.
  • Il ne peut y avoir qu’un seul mouvement de disques entre deux déplacements du plus petit disque et ce mouvement est imposé par la position du plus petit disque. En effet, si le plus petit des $n$ disques est positionné sur le piquet $X$, alors on considère les disques $d_1$ et $d_2$ du dessus des deux autres piquets $Y$ et $Z$ (si l’un des piquets est vide, on considère le disque vide qui est de taille nulle). Le seul mouvement possible est donc de déplacer le plus petit des disques $d_1$ et $d_2$ au-dessus de l’autre. Pour le mouvement suivant, si l’on ne déplace pas le plus petit des $n$ disques, les disques $d_1$ et $d_2$ se retrouvent dans la position précédente, ce qui est impossible par optimalité de la solution. De plus, on remarque que ce déplacement du plus petit des disques $d_1$ et $d_2$ au-dessus de l’autre est imposé par la position du plus petit des $n$ disques sur le piquet $X$.

On considère maintenant les deux sens de déplacements $A\rightarrow B\rightarrow C\rightarrow A$ ou $A\rightarrow C\rightarrow B\rightarrow A$.

Pour déplacer les $n$ disques d’un piquet vers le piquet suivant dans le sens $S$ en utilisant $\mathrm{T}(n)$ mouvements, on procède de la manière suivante :

  • si $n$ est impair, on déplace le plus petit disque une fois sur deux et toujours dans le sens $S$,
  • si $n$ est pair, on déplace le plus petit disque une fois sur deux et toujours dans l’autre sens que $S$.

Preuve

Ce résultat est évident pour $n=1$. Supposons qu’il soit vrai pour déplacer $\ n-1$ disques et montrons-le pour le déplacement de $\ n$ disques. Pour déplacer $\ n$ disques du piquet $X$ vers le piquet $Y$, en supposant que l’on considère le sens $\ S:X\rightarrow Y\rightarrow Z\rightarrow X$, et en utilisant $\ \mathrm{T}(n)$ mouvements, on procède ainsi :

Supposons que l’on déplace toujours le plus petit disque une fois sur deux et toujours dans le sens $\ S$. Puisque le résultat est supposé vrai pour $\ n-1$ disques et que $\ n-1$ est de parité inverse de $\ n$, les $n-1$ plus petits disques sont donc déplacés du piquet $X$ vers le piquet suivant dans l’autre sens que $S$, soit le piquet $Z$, par $\mathrm{T}(n-1)$ mouvements. Remarquons que $\mathrm{T}(n-1)$ est impair et que le mouvement suivant sera donc celui du plus grand disque qui sera déplacé du piquet $X$ vers le piquet $Y$. On continue les déplacements avec le plus petit disque et, toujours car l’on a supposé le résultat vrai pour $\ n-1$ disques et que $\ n-1$ est de parité inverse de celle de $\ n$, on déplace les $\ n-1$ plus petits disques du piquet $Z$ par le piquet suivant dans l’autre sens que $\ S$, soit le piquet $Y$, également par $\ \mathrm{T}(n-1)$ mouvements.

Au final, on a donc bien déplacé les $n$ disques du piquet $X$ vers le piquet $Y$ en $2\mathrm{T}(n-1)+1=\mathrm{T}(n)$ mouvements.

La solution optimale du problème des tours de Hanoï pour $n$ disques est ainsi obtenue par la méthode suivante :

  • si $n$ est impair, on déplace le plus petit disque une fois sur deux toujours dans le sens $A\rightarrow C\rightarrow B\rightarrow A$,
  • si $n$ est pair, on déplace le plus petit disque une fois sur deux toujours dans le sens $A\rightarrow B\rightarrow C\rightarrow A$.

Pour illustrer ceci, voici la solution optimale en $255$ mouvements du problème à $8$ disques où le plus petit disque, représenté en rouge, est toujours déplacé dans le sens $A\rightarrow B\rightarrow C\rightarrow A$.

La conjecture au prochain trimestre

Cela conclut cette présentation du problème classique des tours de Hanoï. Dans la seconde partie de cet article qui paraîtra le trimestre prochain, nous nous intéresserons à la généralisation de ce problème qui consiste à déplacer une tour de disques non plus à l’aide de trois piquets mais avec quatre piquets et plus. Nous énoncerons notamment la conjecture de Frame et Stewart qui porte sur le nombre optimal de mouvements de disque pour cette généralisation.

Post-scriptum :

L’auteur tient à remercier les responsables de cette rubrique Shalom Eliahou et Bruno Martin, ainsi que les relecteurs Fabien Lange, Daniel Massart, QuentinB et ysf.zrir pour leur relecture attentive et leurs conseils avisés.

Article édité par Shalom Eliahou

Notes

[1Henri de Parville, La Nature 566 (1884), p. 285.

[2E. Lucas, Récréations mathématiques, tome 3, p. 55-59, 1893.

Partager cet article

Pour citer cet article :

Jonathan Chappelon — «Les tours de Hanoï I : le problème classique» — Images des Mathématiques, CNRS, 2016

Commentaire sur l'article

  • Les tours de Hanoï I : le problème classique

    le 21 juin à 14:16, par projetmbc

    Bonjour.

    Merci pour cet article très bien rédigé.

    Un souci par contre... Ne devrait-on pas associer une taille infinie à un piquet vide afin de pouvoir y déposer n’importe quel disque ? De plus d’un point de vus informatique, ceci permet de ne pas avoir à traiter différemment les piquets vides.

    Répondre à ce message
    • Les tours de Hanoï I : le problème classique

      le 22 juin à 09:47, par Jonathan Chappelon

      Bonjour,

      Merci pour votre message. Ici nous n’associons pas de taille aux piquets, uniquement les disques ont des tailles différentes. Je comprends toutefois en partie ce que vous voulez dire. On peut en effet supposer qu’à la base de chaque piquet il y ait un disque de taille infinie, ce qui permet de déposer n’importe quel autre disque de taille finie sur celui-ci. Personnellement je ne vois pas ce que cela peut apporter au problème et je ne pense pas que considérer des piquets vides en soit un non plus. Si je n’ai pas bien saisi ce dont vous vouliez parler, je vous remercie d’avance de préciser.

      Répondre à ce message
  • Dernière récurrence

    le 21 juin à 14:45, par projetmbc

    Il me semble que l’on doit commencer la récurrence à $n = 2$ car pour $n=1$ on a un seul mouvement et aucun des deux sens de parcours proposés ne permet d’aller directement de A à C. En espérant ne pas avoir dit de bêtises...

    Répondre à ce message
    • Dernière récurrence

      le 22 juin à 09:53, par Jonathan Chappelon

      Bonjour,

      Merci pour votre commentaire. Nous parlons ici de la dernière preuve de l’article. Pour déplacer une tour de $n=1$ disque d’un piquet $X$ vers un piquet $Y$, il suffit de déplacer cet unique disque dans le même sens : du piquet $X$ au piquet $Y$. Pourriez vous expliquer plus en détails ce qui vous dérange avec ce cas ?

      Répondre à ce message
  • Les tours de Hanoï I : le problème classique

    le 4 juillet à 20:25, par orion8

    Résolution par un robot : https://www.youtube.com/watch?v=SEMfUE5K35I

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM