tour de hanoi coups minimum

• Boites secrètes
• Casse-tête et Puzzle
• Jeux multi et famille
• Coffrets bois
• COFFRETS / CADEAUX
• JEUX DE RÉFLEXION
• CASSE-TÊTE ENFANTS
• CASSE-TÊTE EN MÉTAL
• CUBE / AUTRES FORMES
• CASSE-TÊTE BOUTEILLE
• HANAYAMA Métal

Règle du jeu : La Tour de Hanoï

• 45745 views

La Tour de Hanoï, présentation et règles du jeu.

La Tour de Hanoï est un grand classique dans l'univers des casse-têtes. Vous en avez certainement déjà croisé une ! Malgré les différentes variantes et formes existantes, le but reste le même : déplacer la Tour en un minimum de coups d'un point A à un point B. Mais pas si simple !

La Tour de Hanoï est un puzzle, ou jeu mathématique, inventée en 1883 par Édouard Lucas, arithméticien français né à Amiens, professeur à Saint-Louis, et connu notamment pour ses travaux sur la théorie des nombres et ses Récréations mathématiques . Il prouvera d'ailleurs sa passion pour les jeux mathématiques et de réflexion en commercialisant son casse-tête sous le nom de N. Claus de Siam , professeur au collège de Li-Sou-Stian et prétendument son ami. Mais pour les plus perspicaces d'entre vous, vous aurez compris que ce pseudonyme est en réalité l'anagramme de son nom ( Lucas d'Amiens ) et de la ville où il enseignait ( Saint-Louis ).

Les Tours de Hanoï sont également connues sous le nom de Tours de Lucas ( vous savez maintenant pourquoi ! ), ou Tours de Brahma. Brahma était le dieu créateur-démiurge de l'hindouisme, le premier membre de la Trimūrti, la trinité des déités hindoues majeures. Les autres membres sont Vishnou et Shiva.

La légende se passe au cœur du temple Kashi Vishwanath. Elle raconte que Brahma, au commencement des siècles, apporta dans ce temple, sous le dôme doré au centre du monde, 3 aiguilles de diamant, plantées dans une dalle de bronze, et 64 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.

Les règles de Brahma sont simples : les prêtres doivent déplacer la tour de la première à la troisième aiguille, en ne déplaçant qu'un disque à la fois. Le disque déplacé doit l'être sur l'une des 2 autres aiguilles, et ne doit jamais être placé au-dessus d’un disque plus petit que lui. 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 sur la troisième. Lorsque les prêtres auront terminé, la tour et le temple tomberont, et ce sera la fin des mondes !

Si nous étudions les algorithmes de résolution de la Tour, le nombre de mouvements nécessaires pour déplacer les 64 disques de la première à la troisième colonne est de 18.446.744.073.551.615. Si on considère que les prêtres mettent 1 seconde pour déplacer 1 disque, il faudra plus de 5 milliards de siècles ( 5.845.580.504 exactement ! ) pour terminer la Tour. La fin du monde est encore loin !

A travers cette légende, certains pensent que Lucas fait ici encore parler sa passion pour les jeux et la réflexion.

Pas d'anagramme cette fois, mais des similitudes troublantes entre le nom du temple « Kashi Vishwanath » et le nom de l'ex champion du monde d'échec indien Viswanathan Anand. Et que dire de sa version géante de la Tour de Hanoï avec ses 64 disques … 64 … qui correspond au nombre de cases d'un échiquier …

RÈGLE DU JEU

On dispose de 3 piquets fixés sur un socle, et d'un nombre n de disques de diamètres différents. Les disques sont empilés sur un piquet, en commençant du plus large au plus petit. Le nombre de disques peut varier. Plus il y a de disques au départ, plus le jeu est difficile.

Déplacer les disques d'une tour de 'départ' à une tour 'd'arrivée' en passant par une tour 'intermédiaire', et ceci en un minimum de coups.

2 règles simples :

- on ne déplace qu’un seul disque à la fois, et le disque déplacé doit l'être sur l’un des deux autres piquets au choix ; c’est ce que l’on appelle un déplacement.

- le disque déplacé ne doit jamais être placé au-dessus d’un disque plus petit que lui.

La solution générale est donnée par l'algorithme suivant.

Algorithme récursif

La solution de base du jeu de la Tour de Hanoï est formulée de manière récursive. Étiquetez les piquets avec A - B - C et numérotez les disques de 1 (le plus petit) à n (le plus grand). L'algorithme est exprimé comme suit:

1. Déplacez les n-1 premiers disques de A à B. (Cela laisse le disque n seul sur le piquet A) 2. Déplacez le disque n de A à C 3. Déplacez les n-1 disques de B à C

Pour déplacer n disques, il faut effectuer une opération élémentaire (déplacement d'un seul disque) et une opération complexe, c'est-à-dire le mouvement de n-1 disques. Cependant, cette opération se résout également de la même manière, en demandant comme opération complexe le déplacement de n-2 disques. En itérant ce raisonnement on réduit le processus complexe à un processus élémentaire, c’est-à-dire le déplacement de n-(n-1)=1 disque. C'est un algorithme récursif de complexité exponentielle.

Il est intéressant de noter que le casse-tête peut être résolu pour n'importe quel "n", avec une démonstration par récurrence: supposons que nous ayons une tour en A composée de N disques, et supposons que N soit le nombre de disques maximum autorisés à résoudre le jeu. Au terme du déplacement de la tour de A à B, nous ajoutons à A un disque supplémentaire, de taille égale à N+1, et supposons que ce disque ait été arrêt tout le temps sous les autres. À ce stade, nous déplaçons simplement le disque de A à C, et nous pourrons certainement déplacer la tour de B à C en suivant les mêmes étapes que celles qui étaient nécessaires pour le faire de A à B. Après avoir montré qu’une tour de N disques peut être déplacée d’une colonne à une autre, il est également montré qu’on peut déplacer une tour de N+1 disques.

Aspects psychologiques

Ce casse-tête est utilisé en particulier dans la recherche psychologique, à travers la résolution des problèmes. Il est également utilisé comme test neuropsychologique.

Ce test peut détecter les mauvais fonctionnements des zones frontale et préfrontale et permet d’évaluer les fonctions exécutives telles que la planification, le travail, la mémoire et l’inhibition. La résolution du jeu de la Tour de Hanoï dépend de l'activité inhibitrice, de la "mémoire de travail", c'est-à-dire l'utilisation de la mémoire à court terme, de la mémoire procédurale et de l'intelligence fluide. Ce test est similaire à celui de la Tour de Londres, ainsi qu'à celui des Tours de Toronto, utilisé avant tout pour évaluer les compétences de décision stratégique et résolution de problèmes chez les enfants de 4 à 13 ans et pour étudier les effets du vieillissement sur la résolution des problèmes simples.

Le casse-tête de la Tour de Hanoï est très joué en ligne, on peut trouver de nombreuses réalisations pour ce jeu, en Flash et en Java.

Related products

3 casse-têtes en bois - coffret cadeau - jeu casse-tête plusieurs niveaux, carré royal casse-tête composé de plusieurs essences de bois, jeu de logique et réflexion en bois les 5 différents, jumanji escape room le jeu, édition familiale escape game 3 aventures, tour de hanoi 7 pièces casse-tête en bois.

En poursuivant votre navigation , vous acceptez l'utilisation de cookies.

Outils mathématiques pour le lycée

Grand oral : les tours de hanoï.

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…
• 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.

• 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_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\)
• Montrer que la suite \((x_n)\) est géométrique
• Exprimer \(x_n\) puis \(t_n\) en fonction de \(n\)

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.
• Soit \(r\) un réel. \(r=2r+1 \Leftrightarrow -r = 1 \Leftrightarrow r=-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\)

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
• 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, 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

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
• 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.

Partager cette page :

J’aime ça :, entrées similaires:.

Laisser un commentaire Annuler la réponse

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Commentaire *

Enregistrer mon nom, mon e-mail et mon site dans le navigateur pour mon prochain commentaire.

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

« 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. \]

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.
• 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. \]

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$.

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.

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.

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

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

Partager cet article

Pour citer cet article :.

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

Commentaire sur l'article

Le 21 juin 2016 à 14:16, par projetmbc.

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.

le 22 juin 2016 à 09:47, par Jonathan Chappelon

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.

Dernière récurrence

Le 21 juin 2016 à 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...

le 22 juin 2016 à 09:53, par Jonathan Chappelon

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 ?

le 4 juillet 2016 à 20:25, par orion8

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

le 3 décembre 2019 à 12:03, par hbx444

Pour 3 disques le déplacement de A->B->C ne marche pas puisque l’on obtient un nombre minimum de coup supérieur à 7. Alors comment on fait. Et si on doit faire un algo. récursif comment doit-on tenir compte de se problème.

Laisser un commentaire

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.

Connexion |  s’inscrire |  mot de passe oublié ?

Articles suggérés

Si vous avez aimé cet article, voici quelques suggestions automatiques qui pourraient vous intéresser :

Maître de Conférences, Institut de Mathématiques Alexander Grothendieck, Université de Montpellier.

Voir les commentaires (6)

L'image du jour.

Un article au hasard

Actualités des maths.

• 18 décembre 2023 Séminaire « Mathématiques et poésie, le fond et la forme » 7e séance le mercredi 20 décembre 2023
• 12 décembre 2023 Séminaire « Mathématiques et poésie, le fond et la forme » 6e séance le mercredi 13 décembre 2023
• 4 décembre 2023 Séminaire « Mathématiques et poésie, le fond et la forme » 5e séance le mercredi 6 décembre 2023
• 20 novembre 2023 Séminaire « Mathématiques et poésie, le fond et la forme » 4e séance le mercredi 22 novembre 2023
• 13 novembre 2023 Séminaire « Mathématiques et poésie, le fond et la forme » 3e séance le mercredi 15 novembre 2023
• 6 novembre 2023 Journée Tangente 2023 le 3 décembre 2023

• Énigmes
• Conférences

Les tours de Hanoï

Réfléchissons un peu ensemble....

Si vous avez bien cherché, vous avez dû trouver le nombre de coups minimum pour déplacer 1, 2, 3 ou 4 disques. Remarquez-vous quelque chose? (Indice : ajoutez 1 à chacun de ces nombres).

Si vous ne remarquez rien, peut-être est-ce parce que vous n'avez pas trouvé le nombre minimum ? Cherchez encore ou si vous êtes prêt à tricher, regardez ici .

Maintenant que vous avez remarqué quelque chose, il faudrait savoir s'il s'agit d'une coincidence ou si ça marche pour un nombre plus grand de disques.

Pour cela, nous allons procéder par induction, i.e. faire une démonstration par récurrence : Si l'on sait que le nombre minimum de coups pour déplacer une pile de n disques est C , combien en faudra-t-il pour une pile de (n+1) disques ?

On sait que l'on peut déplacer les n disques du haut vers la position intermédiaire en C coups. Maintenant, il est possible de déplacer le disque du bas sur la position finale. Enfin, il faut remettre les n disques du haut par-dessus. Cela prend encore C coups. Ainsi, on peut bouger la pile de (n+1) disques en (2C + 1) coups.

Attention ! Est-ce bien le nombre minimum de coups ou est-ce qu'on aurait pu mieux faire ? Réfléchissez un peu. Il va falloir à un moment ou un autre déplacer le disque du bas. Que faut-il faire auparavant ? Combien de coups cela prend au minimum ? Que faut-il faire une fois le disque du bas déplacé ? Combien de coups cela prend au minimum ?

Finalement, on a vu que s'il faut au moins c n coups pour déplacer n disques, il en faut au moins c n+1 = 2c n + 1 pour (n + 1) disques. Ce n'est pas mal, mais on voulait une formule en fonction de n .

D'après vos premiers essais, vous avez probablement conjecturé que c n = f(n) où f(n) est une fonction de n que vous avez déterminée. Si vous n'aviez pas assez de chiffres pour faire une conjecture, vous pouvez maintenant en avoir plus. Par exemple, pour 5 disques, il faut au moins 2x15 + 1 = 31 = 2 5 - 1.

• Il faut d'abord montrer que c'est vrai pour n = 1 . A-t-on c 1 = f(1) ?
• Maintenant, il faut montrer que si c'est vrai pour n = k , c'est aussi vrai pour n = k+1, i.e. que si c k = f(k) , alors c k+1 = f(k+1) . Comme on a vu que c k+1 = 2c k + 1 , il suffit de vérifier que f(k+1) = 2f(k)+1 .

La prophétie va-t-elle se réaliser ?

Sachant que les moines ont n = 64 disques à déplacer, même en déplacant un disque par seconde, il leur faudra 2 64 - 1 secondes, i.e. au moins (2 64 - 1) / (60x60x24x366) > 2 38 années.

La prophétie a donc de grandes chances de se réaliser !!!

Il fallait trouver 1, 3, 7 et 15. En ajoutant 1, on obtient donc 2 = 2 1 , 4 = 2 2 , 8 = 2 3 et 16 = 2 4 .

Les tours de Hanoï

• on déplace un seul disque à la fois,

Free JavaScripts provided by The JavaScript Source

Passé, présent : partager et faire aimer les mathématiques

Filtres de recherche

La tour de Hanoï

Édouard Lucas

Création : 1882

Auteurs/contributeur(s) : Édouard Lucas

Chaque mois, nous vous proposons un support coup de cœur, une référence, une nouveauté... Coup de projecteur qui en inspirera peut-être quelques-uns.

Marmit – Région Centre

Responsable : Pierrick Bideau-Sorita

Affaire de logique – Le Monde

Mickaël Launay

Michel Talagrand

VideoDiMath 2024

Amandine Aftalion

Accromath 2023-2

Concours bulles au carré 2024

Nadège Arnaud

Maths et images, question de point de vue

IREM de Poitiers

Pourquoi est-on penché dans les virages ?

Le théorème de Marguerite

Anne Novion

Vous reprendrez bien un peu de maths ?

Claire Lommé

Hugo Duminil-Copin

Médailles Fields 2022

Malle à Maths

Institut Denis Poisson - Centre•Sciences

Mathématiques dans le noir

Michel Coornaert

Les algorithmes font-ils la loi ?

Aurélie Jean

la diagonale du fou

Abstract Strategy Games - Giant Kites - Sky Drum

The Towers of Hanoi

• Pour 3 disque s , leurs déplacements sont faisables au minimum en 7 coups .
• Pour 4 disques , leurs déplacements sont faisables au minimum en 15 coups .
• Pour 5 disques , leurs déplacements sont faisables au minimum en 31 coups .
• Pour 6 disques , leurs déplacements sont faisables au minimum en 63 coups .
• Pour 7 disques , leurs déplacements sont faisables au minimum en 127 coups .
• Pour 8 disques , leurs déplacements sont faisables au minimum en 255 coups .

ABSTRACT STRATEGY GAMES

Chess Variants

Checkers Variants

Abstract Games

GIANT KITES

Kites in the Sky

Building Plan

Learn to Play Kites

SOUNDS FROM SKY

total pageviews

My websites.

• Borobudur, carnet de voyage
• les lettres de la mousson
• Parkinson, Inside...
• The Bead Games
• Le Jeu Scènique pour la Paix
• Jean-Louis Cazaux
• Carl W.Cole, Soul Brother
• Trichess, Key Reference of Chess for 3
• Les Jeux Abstraits de Papatilleul
• Klubo Internacia de Bao Amantoj
• All Work No Play...
• Marie-Ange Guilleminot
• Terre et Son
• Ecoutez Voir

Les tours de Hanoï

Méthode 1 Calculatrice

Méthode 2 Python

Une erreur sur la page une idée à proposer .

Nos manuels sont collaboratifs, n'hésitez pas à nous en faire part.

Oups, une coquille

j'ai une idée !

Nous préparons votre page Nous vous offrons 5 essais

• Recherche par auteur ou oeuvre
• Recherche par idée ou thème
• Recherche par mot clé
• Détecteur de plagiat
• Commande & correction de doc
• Publier mes documents

Consultez plus de 218779 documents en illimité sans engagement de durée. Nos formules d'abonnement

Vous ne trouvez pas ce que vous cherchez ? Commandez votre devoir, sur mesure !

• Matières scientifiques & technologiques
• Mathématiques
• Présentation

Comment résoudre la légende des tours de Hanoï à l'aide de la récurrence ? - Grand Oral de Mathématiques

Thèmes abordés.

Légende des tours de Hanoï, suites, Grand oral , suites récurrentes

Résumé du document

Bienvenue à ce grand oral de la spécialité maths, où nous allons nous intéresser à la résolution de la légende des tours de Hanoï à l'aide de la récurrence, dans le cadre du chapitre des suites. Les tours de Hanoï sont un célèbre puzzle mathématique qui consiste à déplacer une tour de disques d'un piquet de départ à un autre, en utilisant un troisième piquet comme intermédiaire. Cette légende, apparue en 1883, a suscité l'intérêt de nombreux mathématiciens au fil du temps, qui ont cherché à résoudre ce casse-tête. Nous allons voir comment la récurrence peut être utilisée pour résoudre ce problème et comment les suites peuvent être utilisées pour analyser le nombre de déplacements nécessaires pour résoudre le problème en fonction du nombre de disques.

• Comment la récurrence peut-elle être utilisée pour résoudre ce problème ?
• Comment les suites peuvent-elles être utilisée pour analyser le nombre de déplacements nécessaires pour résoudre le problème en fonction du nombre de disques ?

[...] Conclusion En conclusion, nous avons vu comment utiliser la méthode de la récurrence pour résoudre la légende des tours de Hanoï et comment les suites peuvent être utilisées pour analyser le nombre de déplacements nécessaires pour résoudre le problème en fonction du nombre de disques. Nous avons également souligné l'importance de la récurrence dans la résolution de problèmes mathématiques, en particulier dans le domaine des suites. En utilisant cette méthode, nous avons pu trouver une formule générale pour calculer le nombre de déplacements nécessaires pour résoudre le problème avec n disques. Enfin, cette méthode illustre l'importance de la créativité et de la réflexion dans la résolution de problèmes mathématiques, ainsi que la beauté et l'utilité des mathématiques dans la vie quotidienne. [...]

[...] Cette relation peut être établie comme suit : Cas de base : si n = le nombre de coups nécessaires est égal à 1. Cas général : supposons que nous ayons déjà résolu le problème pour n-1 disques. Pour déplacer n disques, nous devons d'abord déplacer les n-1 disques supérieurs sur une tour auxiliaire, puis déplacer le disque n sur la tour de destination, et enfin déplacer les n-1 disques supérieurs sur le disque n. Le nombre total de coups nécessaires est donc égal à 2 fois le nombre de coups nécessaires pour déplacer n-1 disques, plus 1. [...]

[...] Comment résoudre la légende des tours de Hanoï à l'aide de la récurrence ? Introduction Bienvenue à ce grand oral de la spécialité maths, où nous allons nous intéresser à la résolution de la légende des tours de Hanoï à l'aide de la récurrence, dans le cadre du chapitre des suites. Les tours de Hanoï sont un célèbre puzzle mathématique qui consiste à déplacer une tour de disques d'un piquet de départ à un autre, en utilisant un troisième piquet comme intermédiaire. [...]

[...] Pour ce faire, nous allons utiliser la récurrence. La première étape consiste à déplacer les n disques supérieurs de la tour de départ à la tour intermédiaire en utilisant la tour d'arrivée comme tour intermédiaire. Le nombre de déplacements nécessaires est le même que le nombre de déplacements nécessaires pour résoudre le problème à partir de n disques. Ensuite, nous déplaçons le disque restant de la tour de départ à la tour d'arrivée. Le nombre de déplacements nécessaires pour cette étape est 1. [...]

[...] La résolution de la légende des tours de Hanoï à l'aide de la récurrence est basée sur l'étude d'une suite. Cette suite représente le nombre minimal de déplacements nécessaires pour résoudre le problème en fonction du nombre de disques. Pour étudier cette suite, nous allons utiliser la récurrence. Prenons le cas le plus simple où il n'y a qu'un seul disque. Dans ce cas, il suffit de déplacer le disque de la tour de départ à la tour d'arrivée. Le nombre de déplacements nécessaires est donc 1. [...]

• Nombre de pages 3 pages
• Langue français
• Format .docx
• Date de publication 19/06/2023
• Consulté 6 fois
• Date de mise à jour 03/07/2023

Source aux normes APA

Lecture en ligne

Contenu vérifié

Les plus consultés

• Etude et modélisation de la trajectoire d'une balle de tennis
• Quelle est l'utilité des équations différentielles ? (Sujet de grand oral)
• Comment la convexité permet-elle d'optimiser certains marchés économiques ?
• Comment les mathématiques peuvent-elles être mises au service de la criminalistique ? - Grand oral de Mathématiques
• Comment déterminer l'heure de décès d'un cadavre à l'aide de sa température ? - Grand oral de Mathématiques

Les plus récents

• Statistiques et théorie des probabilités
• Suites et fonctions
• Les probabilités - Exercice corrigé niveau bac
• Les suites - Exercice corrigé niveau bac
• Géométrie dans l'espace - Exercice corrigé niveau bac

We can help you reset your password using the email address linked to your Project Euclid account.

• Subscription and Access
• Library Resources
• Publisher Tools
• Researcher Resources
• About Project Euclid
• Advisory Board
• News & Events
• DOWNLOAD PAPER SAVE TO MY LIBRARY

In the four-peg variant of the Towers of Hanoï game, it is well known that $N$ disks can be transferred from a column to another in $2^{\nabla0}+2^{\nabla 1}+\cdots+2^{\nabla(N-1)}$ moves, where $\nabla n$ denotes the largest integer $p$ such that $p(p+1)/2\leqslant n$, and it was conjectured that this number of moves was the minimum possible. We shall see, in this article, that is is indeed the case.

Dans la variante à quatre colonnes des Tours de Hanoï, on sait bien qu'on peut transférer $N$ disques d'une colonne vers une autre en $2^{\nabla 0}+2^{\nabla 1}+\cdots+2^{\nabla(N-1)}$ mouvements, où $\nabla n$ désigne le plus grand entier $p$ tel que $p(p+1)/2\leqslant n$, et on conjecturait que ce nombre de mouvements était le minimum possible. Nous verrons, dans cet article, que c'est effectivement le cas.

Thierry Bousch. "La quatrième tour de Hanoï." Bull. Belg. Math. Soc. Simon Stevin 21 (5) 895 - 912, december 2014. https://doi.org/10.36045/bbms/1420071861

Information

zbMATH: 1307.05006 MathSciNet: MR3298485 Digital Object Identifier: 10.36045/bbms/1420071861

Subjects: Primary: 05C12

Keywords: Conjecture de Frame-Stewart , Tours de Hanoï

Rights: Copyright © 2014 The Belgian Mathematical Society

KEYWORDS/PHRASES

Publication title:, publication years.

•   A la Une
•   Archives
• Technologies
•   Aéronautique
•   Transports
•   Espace
•   Energie
•   Multimédia
•   Architecture
•   Mathématiques
•   Physique
•   Astrophysique
•   Astronomie
•   Vie et Terre
•   Autres Sujets
•   Rétro
•   En ce moment
•   Codes promo Amazon FR
•   Codes promo Amazon US
•   Codes promo Banggood
•   Codes promo DHgate
•   Boutique
• Encyclopédie ✕
• Forum 💬 ✕

Tours de Hanoï - Définition

Nombre de déplacements à effectuer.

Il est facile de démontrer par récurrence que si N est le nombre de disques, il faut 2 N - 1 coups au minimum pour parvenir à ses fins, quantité qui augmente très rapidement avec N . En effet, soient a , b et c les trois emplacements des tours. Notons x N le nombre de déplacements de disques nécessaires au déplacement d'une tour complète. Pour déplacer une tour de N disques de a vers c , on déplace la tour des N -1 premiers disques de a vers b , puis le disque N de a vers c , puis la tour des N -1 disques de b vers c . Le nombre de déplacements de disques vérifie donc la relation de récurrence :

ce qui donne bien

Codage des positions

Nous avons vu que, si p est impair, le p -ème coup consiste à déplacer le plus petit disque. Nous avons également vu que le déplacement du petit disque était cyclique. Par ailleurs, si p est pair, on vient de déplacer un autre disque, le plus petit disque ayant été déplacé au coup p -1 ; le disque que l'on vient de déplacer au coup p l'aurait été au coup p ⁄ 2 s'il n'y avait eu que N-1 disques.

Il résulte de ces préliminaires que, pour connaître la disposition des disques après le p -ème déplacement, il suffit de procéder comme suit.

Notons d(N, p ) la position du plus petit disque après le p -ème coup ( p impair), on a :

Notons E(N, p ) la suite des emplacements occupés par les N disques, du plus grand au plus petit, après p mouvements. On a alors, en notant par un point la concaténation entre deux listes de lettres :

Par exemple, la position au 12 e coup avec 4 disques est :

Résolution itérative

Il existe également une procédure itérative pour résoudre le problème des tours de Hanoï . Elle consiste à effectuer successivement les deux déplacements suivants, en désignant par A, B, C les trois tours :

• déplacer le plus petit disque d'un emplacement à l'emplacement suivant (de A vers B, de B vers C, de C vers A, par exemple)
• déplacer un autre disque

et à poursuivre itérativement ces deux déplacements jusqu'à ce que la tour complète soit déplacée, le dernier déplacement se limitant alors à celui du plus petit disque sur le sommet de la tour. L'action déplacer un autre disque est non ambigüe puisque, en dehors du plus petit disque, un seul mouvement d'un autre disque est possible.

Contrairement à la procédure récursive, la procédure itérative n'utilise aucune mémorisation de l' arbre des déplacements à effectuer et nécessite seulement de se souvenir si on doit déplacer le plus petit disque ou non, et dans quel sens sont effectués les déplacements du petit disque. Il permet également, à tout moment, de revenir à la situation de départ : il suffit pour cela d'inverser le sens dans lequel se déplace le plus petit disque. Par contre, les raisons pour lesquelles cet algorithme résout le problème sont moins apparentes que pour l' algorithme récursif .

Supposons que la tour soit initialement sur l'emplacement A, et qu'on veuille la déplacer sur l'emplacement B. Nous allons montrer par récurrence sur le nombre N de disques à déplacer que l'itération des deux mouvements décrits précédemment répond à la question, le sens dans lequel est déplacé le plus petit disque étant A → C → B → A → … → B si N est pair, et A → B → C → A → … → B si N est impair. En effet :

• Pour N = 1, il suffit de déplacer l'unique disque de A vers B. Supposons la propriété démontrée pour le déplacement de N-1 disques. Comme dans le cas récursif, on va déplacer la tour de N disques en déplaçant les N-1 disques supérieurs de A vers C, puis le grand disque de A vers B, puis les N-1 disques de C vers B.
• Si N est pair, alors N-1 est impair, et selon l'hypothèse de récurrence (en échangeant les rôles de B et C), lors du déplacement de la pile des N-1 disques supérieurs de A vers C, un déplacement sur deux est effectué par le plus petit disque dans l'ordre A → C → B → A → … → C. On déplace alors le grand disque de A vers B (déplacement qui succède au dernier déplacement du plus petit disque). Puis on déplace les N-1 disques de C vers B, un déplacement sur deux étant effectué par le plus petit disque, cette fois dans l'ordre C → B → A → C → … → B. Finalement, la suite des déplacements du petit disque aura bien été A → C → B → A → … → C → B → A → C → … → B, le plus petit disque étant déplacé une fois sur deux.
• On procédera à une vérification analogue si N est impair.

À propos des cookies sur ce site

Ce site utilise des cookies pour améliorer votre expérience en ligne. Si vous continuez à utiliser ce site sans modifier vos préférences de cookies, nous en conclurons que vous marquez votre accord quant à notre utilisation de cookies. Pour en savoir plus ou pour modifier vos préférences de cookies, consultez notre politique relative aux cookies

CogniFit - Test de la tour de Hanoï

Pour mon propre entraînement

Pour suivre des patients

Pour un membre de ma famille

Pour suivre des élèves

Pour des recherches

Bien-être des employés

Développeurs

Vous allez créer un compte personnel. Ce type de compte est conçu pour vous aider à évaluer et à entraîner vos capacités cognitives.

Vous allez créer un compte de gestion des patients. Ce compte a pour vocation d'aider les professionnels de santé (médecins, psychologues...) dans le diagnostic et la stimulation cognitive.

Vous allez créer un compte familial. Ce compte est conçu pour permettre aux membres de votre famille d'accéder aux évaluations et aux entraînements de CogniFit.

Vous allez créer un compte de recherche. Ce compte est spécialement conçu pour aider les chercheurs dans leurs études dans les domaines cognitifs.

Vous allez créer un compte de gestion des étudiants. Ce compte est conçu pour aider au diagnostic et à l'intervention des troubles cognitifs chez les enfants et les jeunes étudiants.

Vous allez créer un compte de gestion d'entreprise. Ce compte est conçu pour permettre à vos employés d'accéder aux évaluations et à la formation CogniFit.

Vous allez créer un compte développeur. Ce compte est conçu pour intégrer les produits CogniFit au sein de votre entreprise.

Pour votre propre usage (à partir de 16 ans)

Envoyez des évaluations et des entraînements à vos patients

Envoyez des évaluations et des entraîenements à vos étudiants

Envoyez des évaluations et des entraînements à vos enfants ou vos proches

Envoyez des évaluations et des entraînements aux personnes participant à vos recherches

En cliquant sur "Inscrivez-vous", vous acceptez nos Conditions d’utilisation et vous reconnaissez avoir lu et accepter notre Politique de Confidentialité des données.

Les références

Hinz, A. (1989). "The Tower of Hanoi". L'Enseignement Mathématique. 35: 289–321. doi:10.5169/seals-57378.

App CogniFit

• Nous suivre

Votre cerveau

• Cerveau et esprit
• A propos du cerveau
• Les parties du cerveau
• Plasticité neuronale
• Perte de Mémoire
• Déficience intellectuelle
• Functions cérébrales
• Validation thérapeutique numérique
• Jeux d'ordinateur
• Adultes en bonne santé
• Évaluation holistique
• Personnes âgées en bonne santé (iTV)
• Entraînement adultes âgés
• État cognitif chez les personnes âgées
• Révision systémique
• Taxonomie SG4D
• Jeux pour le cerveau
• Échecs en ligne
• Mini-mots croisés
• Fruit Frenzy
• Crystal Miner
• Robo Factory
• Neon Lights
• Rends moi fou
• mots croisés visuels
• Faîtes la paire
• Space Rescue
• Chaos mathématique
• Course de billes
• Tennis mélodique
• Trouvez votre animal de compagnie
• Paires musicales
• Chronocolor
• Aventures de grenouille
• Pingouin Explorateur
• Abeille de Couleur
• Jeux d'agilité mentale
• Jeux en ligne pour la mémoire
• Développement cognitif
• Exercice cérébral
• Quizz pour la tête
• Exercices pour l'esprit
• Entraînement cérébral personnalisé
• Exercice mental
• Jeux mathématiques amusants
• Batailles cérébrales
• Conditions d'utilisation
• Confidentialité
• La Direction de CogniFit
• Salle de presse
• Devenir un affilié
• Nous contacter

Veuillez entrer votre adresse email

Search code, repositories, users, issues, pull requests...

Provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

• Notifications

🐍 Algorithme de la tour de Hanoi en python

franklbt/Hanoi

Folders and files, repository files navigation.

Algorithme de la tour de Hanoi en python

Pour le faire démarrer il a les paramètres en haut du code: draw_all_step = True dessinera toutes les étapes, et pour passer a la suivante une fois le code executé faire alt+f4 sur le graphique (pas trop rapidement, sinon ca plante) sinon si c’est false il dessine la premiere etape et la derniere, le reste sera inscrit dans le log de python.

n_disk est le nombre de disques qui composent une tour

• Python 100.0%