Cet article traitera de l’énigme des trous de Hanoï. Il ne s’agit pas d’un sujet de grand oral donné clé en main, mais simplement d’une présentation du problème et de sa résolution, en lien avec le programme de mathématiques de Terminale Générale.
Il ne tient qu’à vous de sélectionner les informations qui vous semblent pertinentes sur cette page et d’en chercher de nouvelles ailleurs pour constituer votre oral.
Thèmes abordés
- Suites et récurrences
- Un peu de dénombrement pour la variante
- Peut-être choisi pour un oral croisé Mathématiques – NSI
Présentation de l’énigme
L’énigme des tours de Hanoï est un jeu de réflexion imaginé par le mathématicien Edouard Lucas.
Ce jeu est composé de trois piquets ainsi que d’un certain nombre de disques de diamètres différents, originellement tous placés sur le premier piquet. Le but est de transférer ces disques du premier au troisième piquet, en suivant deux règles
- on ne peut déplacer d’un seul disque à la fois ;
- il n’est pas possible de placer un disque sur un autre disque plus petit
Vous pouvez ci-dessous essayer de résoudre cette énigme vous-même avant de vous lancer dans la suite de l’article.
Résolution récursive du problème
Algorithme récursif
Une manière classique pour résoudre l’énigme des tours de Hanoï est de procéder de manière récursive. Nous allons montrer par récurrence que l’énigme du tour de Hanoï à \(n\) disques possède bien une solution.
- Initialisation : Pour 1 disque, il est assez facile de résoudre ce problème…
- Hérédité : Soit \(n\) un entier naturel non nul. Supposons que \(P(n)\) est vraie. Pour déplacer la tour de \(n+1\) disques du piquet 1 au piquet 3, nous procédons ainsi
- Nous déplaçons les \(n\) disques du sommet du piquet A au piquet B. C’est possible en \(t_n\) coups, d’après notre hypothèse de récurrence.
- Nous déplaçons le disque restant du piquet A au piquet C. Cela ne demande qu’un seul coup.
- Nous transférons alors les \(n\) disques du piquet B au piquet C. Cela demande de nouveau \(t_n\) coups.
Les \(n+1\) disques se trouvent finalement sur le piquet C. \(P(n+1)\) est vraie.
- Conclusion : \(P(1)\) est vraie et \(P\) est héréditaire. Par récurrence, \(P(n)\) est vraie pour tout entier naturel non nul \(n\).
Cette démonstration nous permet par ailleurs de déterminer une relation de récurrence sur la suite \((t_n)\), qui est définie ainsi :
\[ \left\{\begin{array}{l}t_1 = 1\ \\
\text{Pour tout entier naturel }n,\, t_{n+1}=2t_n+1\end{array}\right.\]
Nous pouvons alors calculer les premiers termes de la suite \((t_n)\).
- \(t_0=1\)
- \(t_1 = 2t_0+1 = 2 \times 1 +1 = 3\)
- \(t_2 = 2t_1+1 = 2 \times 3 +1 = 7\)
- \(t_3 = 2t_2+1 = 2 \times 7 +1 = 15\)
- \(t_4 = 2t_3+1 = 2 \times 15 +1 = 31\)
Il semblerait que pour tout entier naturel \(n\), \(t_n=2^n -1\). Deux méthodes sont envisageables pour le démontrer
Montrer par récurrence que, pour tout entier naturel non nul \(n\), \(t_n=2^n-1\).
Méthode 2 :
- Déterminer le réel \(r\) tel que \(r=2r+1\)
- Pour tout entier naturel non nul \(n\), on pose \(x_n=t_n-r\)
- Montrer que la suite \((x_n)\) est géométrique
- Exprimer \(x_n\) puis \(t_n\) en fonction de \(n\)
Afficher/Masquer la solution
Méthode 1
Pour tout entier naturel non nul \(n\), nous considèrons la proposition \(P(n)\) : « \(t_n =2^n-1\)».
- Initialisation : Pour \(n=1\), on a \(2^1-1=2-1=1=t_1\). \(P(1)\) est vraie.
- Hérédité : Soit \(n\) un entier naturel non nul. Supposons que \(P(n)\) est vraie.
Alors, \(t_n=2^n-1\). Or, \[t_{n+1}=2t_n+1=2 \times(2^n-1)+1=2 \times 2^n-2+1=2^{n+1}-1\]
\(P(n+1)\) est vraie. - Conclusion : \(P(1)\) est vraie et \(P\) est héréditaire. Par récurrence, \(P(n)\) est vraie pour tout entier naturel non nul \(n\).
Méthode 2
- Soit \(r\) un réel.
\(r=2r+1 \Leftrightarrow -r = 1 \Leftrightarrow r=-1\) - Pour tout entier naturel non nul \(n\), on pose \(x_n=t_n+1\)
- Pour tout entier naturel non nul \(n\),
\[x_{n+1}=t_{n+1}+1=2t_n+1+1=2(t_n+1)=2x_n\]
La suite \((x_n)\) est géométrique de raison 2 - Pour tout entier naturel non nul, on a \(x_n = x_1 \times 2^{n-1}\) c’est-à-dire \(x_n=2 \times 2^{n-1}=2^n\) et donc \(t_n=x_n-1=2^n-1\)
- Pour tout entier naturel non nul \(n\),
Exemple de résolution
Prenons l’exemple de la résolution de l’énigme de la tour à 3 disques. D’après l’algorithme récursif il faut :
- Déplacer les 2 disques du sommet du piquet A au piquet B
- Pour cela,
- on commence par déplacer le disque du sommet du piquet A au piquet C
- On déplace ensuite le deuxième disque du piquet A au piquet B
- On place alors le plus petit disque, situé au piquet C, sur le disque au piquet B
- On peut alors déplacer le disque numéro 3 du piquet A au piquet C
- Il faudra alors déplacer la tour de 2 disques situés au piquet B vers le piquet C
- Pour cela,
- Pour cela, on commence par déplacer le disque du sommet du piquet B au piquet A
- On déplace ensuite le deuxième disque du piquet B au piquet C
- On place alors le plus petit disque, situé au piquet A, sur le disque au piquet C
Les mouvements à effectuer sont donc les suivants
- Disque 1 : A → C
- Disque 2 : A → B
- Disque 1 : C → B
- Disque 3 : A → C
- Disque 1 : B → A
- Disque 2 : B → C
- Disque 1 : A → C
Vers une solution itérative
La résolution récursive possède un grand désavantage : bien que l’on sache qu’il est possible de résoudre le problème, il est difficile d’établir directement et de tête la liste des coups.
Une fois la méthode prise en main, et en augmentant le nombre de disques, on remarque aisément que le plus petit disque est déplacé tous les 2 coups.
En effet, lorsque l’on déplace le petit disque d’un piquet à un autre, il n’y a alors que deux disques de libre. Nous sommes alors obligés de déplacer le plus petit de ces disques sur le plus grand de ceux-là.
Mais alors :
- Il n’est pas possible de déplacer le disque que nous venons de déplacer, sans quoi la solution n’est plus optimale
- Il n’est pas non plus possible de déplacer le disque qui se trouvait en-dessous, puisque les deux autres disques sont plus petits
Le seul choix restant est alors de déplacer le petit disque.
Le nombre total de coups étant de \(2^n -1\) pour la solution optimale, cela signifie que le petit disque se déplace \(2^{n-1}\) fois, que le disque numéro 2 se déplace \(2^{n-2}\) fois et ainsi de suite, jusqu’au plus gros disque qui ne se déplace qu’une fois.
On retrouve ici l’égalité \( 1 + 2 + 4 + \dots + 2^{n-1} = 2^n -1\).
Il suffit alors de savoir les mouvements du plus petit disque pour résoudre de manière itérative le problème des tours de Hanoï. Dans le cas de la résolution avec 3 disques, les mouvements du disque 1 étaient A → C → B → A → C. Pour le problème à 4 disques, les mouvements de ce plus petit disque s’effectueront en revanche dans l’autre sens A → B → C → A …
- Si le nombre \(n\) de disques est impair, déplacer le plus petit disque une fois sur deux dans le sens A → C → B → A
- Si le nombre \(n\) de disques est pair, déplacer le plus petit disque une fois sur deux dans le sens A → B → C → A
Pour les autres coups, effectuer l’unique déplacement possible n’utilisant pas le plus petit disque.
Variante : Passer par toutes les positions
Nous avons jusqu’ici uniquement traiter la solution optimale, c’est-à-dire celle qui demande le moins de coups possibles. Une autre possibilité serait de résoudre le problème des tours de Hanoï en passant par toutes les positions possibles.
Il est possible de placer le plus gros des disques sur n’importe lequel des 3 piquets. Puis, le disque suivant peut lui aussi être placé sur n’importe quel piquet, puisqu’il n’y a pas de disque déjà positionné, et ainsi de suite jusqu’au plus petit.
Une configuration de l’énigme des tours de Hanoï peut être vue comme un \(n\)-uplet de l’ensemble \(\{A;B;C\}\) ou le \(k\)-ième coordonnées désigne l’emplacement du disque numéro \(n-k\). De ce fait, le nombre de configurations valides est de \(3^n\).
Pour les élèves suivant l’option Maths expertes : les positions peuvent alors être placées dans un graphe : deux configurations sont reliées s’il est possible de passer de l’une à l’autre en un seul coup. Trouver une solution au problème de Hanoï qui passerait par toutes les configurations possibles revient donc à trouver un chemin eulérien dans ce graphe, ayant pour départ la configuration AAA…A et pour arrivée la configuration CCC…C
Là encore, il est possible de montrer qu’une solution existe de manière récursive :
- Avec un seul disque, il suffit de passer du piquet A au piquet B puis au piquet C
- Si une solution existe avec \(n\) disques, pour un entier \(n\) quelconque, on procède alors ainsi pour \(n+1\) disques :
- On déplace les \(n\) premiers disques du piquet A au piquet C en passant par toutes les configurations
- On déplace le disque \(n+1\) du piquet A au piquet B
- On déplace les \(n\) disques du piquet C au piquet A, encore une fois en passant par toutes les configurations
- On déplace le disque \(n+1\) du piquet B au piquet C
- On déplace une dernière fois les \(n\) disques du piquet A au piquet C, toujours en passant par toutes les configurations
Sur notre graphe, cela revient à explorer la partie en bas à gauche du graphe, puis à emprunter l’arête bleue reliant ACC à BCC, explorer la partie haute du graphe, emprunter l’arête de BAA à CAA et enfin, explorer la partie en bas à droite du graphe.
Notre algorithme demande, pour la solution à \(n+1\) disques, de déplacer 3 fois une tour de \(n\) disques, et d’y ajouter 2 déplacements d’un seul disque. Si on note \(d_n\) le nombre de déplacements à effectuer pour \(n\) disques en passant par toutes les configurations valides, on aboutit à
\[ \left\{\begin{array}{l}d_1 = 2\ \\
\text{Pour tout entier naturel }n,\, d_{n+1}=3d_n+2\end{array}\right.\]
Les premiers termes de cette suite sont alors 2, 8, 26, 80… Il semblerait que pour tout entier naturel non nul \(n\), \(d_n=3^n-1\), ce qui est bien conforme à notre problème : puisqu’il y a \(3^n\) configurations valides, passer par toutes celles-ci demande \(3^n -1\) déplacements.
