tour de hanoi explication

•   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

Introduction.

Le problème des tours de Hanoï est un jeu de réflexion imaginé par le mathématicien français Édouard Lucas, et consistant à déplacer des disques de diamètres différents 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, tout en respectant les règles suivantes :

• on ne peut déplacer plus d'un disque à la fois,
• on ne peut placer un disque que sur un autre disque plus grand que lui ou sur un emplacement vide .

On suppose que cette dernière règle est également respectée dans la configuration de départ.

Origine du problème

Le problème mathématique des tours de Hanoï a été inventé par Édouard Lucas. Il est publié dans le tome 3 de ses Récréations mathématiques , parues à titre posthume en 1892. Il annonce que ce problème est dû à un de ses amis, N. Claus de Siam , prétendument professeur au collège de Li-Sou-Stian (une double anagramme de Lucas d'Amiens , sa ville de naissance, et Saint Louis , le lycée où Lucas enseignait).

Sous le titre «  Les brahmes tombent  », Lucas relate que «  N. Claus de Siam 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ées 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, 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 du Brahmâ. 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, 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 !  ».

Comme indiqué ci-dessous, un jeu à 64 disques requiert un minimum de 2 64 -1 déplacements. En admettant qu'il faille 1 seconde pour déplacer un disque, ce qui fait 86 400 déplacements par jour , la fin du jeu aurait lieu au bout d'environ 213 000 milliards de jours, ce qui équivaut à peu près à 584,5 milliards d'années, soit 43 fois l'âge estimé de l' univers (13,7 milliards d'années selon certaines sources).

Résolution récursive

Le problème des tours de Hanoï est vu en algorithmique (programmation), où il offre un exemple de la puissance et de la lisibilité des programmes définis de façon récursive (un autre exemple étant le tri arborescent). En effet, la méthode de résolution vue précédemment conduit à un algorithme récursif , décrit ci-dessous. Les paramètres de la procédure Déplacer sont :

On obtient par exemple :

En langage PHP

En langage Python  :

En langage Prolog  :

Au fil des maths

La tour d’hanoï, vive les casse-tête la tour d’hanoï, vous connaissez les auteurs nous présentent ce jeu et s’intéressent à l’aspect mathématique de son fonctionnement reposant sur la numération binaire., michel boutin & frédéric de ligt.

© APMEP Juin 2020

⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅♦⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅

La Tour d’Hanoï 1 est un casse-tête inventé par le mathématicien français Édouard Lucas (1842-1891) qui en a fait don au Conservatoire national des arts et métiers de Paris 2 en 1888. Ce casse-tête est constitué par une planchette sur laquelle on a fixé trois tiges ; sur l’une d’elles on a enfilé huit disques de diamètres décroissants, le plus petit en haut de la pile et le plus grand en bas.

Figure 1 . Tour d’Hanoï sortie de sa boîte, et installée. © Musée des arts et métiers, Cnam, Paris / Photo Michèle Favareille .

L’objectif du joueur est de transposer tous les disques d’une tige à une autre en respectant des règles de déplacement très précises : à chaque coup, le joueur prend un disque sur une tige et l’enfile sur une autre. Celle-ci pourra être soit vide, soit occupée par une pile d’un ou plusieurs disques. Dans ce cas, le joueur ne doit pas recouvrir un disque de diamètre inférieur à celui qu’il est en train de déplacer. Ainsi, un disque, quelle que soit sa grandeur, est toujours posé sur un plus grand que lui.

Un peu d’histoire

La Tour d’Hanoï est le seul jeu inventé par Édouard Lucas qui est entré dans la postérité. La première édition fut commercialisée en 1883 avec ce titre très curieux et apparemment très mystérieux : «La Tour d’Hanoï véritable casse-tête annamite. Jeu rapporté du Tonkin par le professeur N. Claus (de Siam). Mandarin du Collège Li-Sou-Stian !»

Figure 2 . Boîte de la Tour d’Hanoï. (hauteur : 10 cm, largeur : 14,5 cm, longueur : 15 cm, masse : 365 g.) © Musée des arts et métiers, Cnam, Paris / Photo Michèle Favareille .

Le mystérieux professeur N. Claus (de Siam) fut rapidement identifié : il s’agit de Lucas d’Amiens 3 , professeur au lycée Saint-Louis.

Nombre de déplacements

Dans le fascicule n° 3 de la série «Jeux scientifiques», intitulé «La Tour d’Hanoï, jeu tombé de Saturne» paru en 1889 [2 , 3] sous le chapitre «L’exposant des puissances», Lucas donne une méthode simple pour calculer le nombre \(N\) de déplacements selon le nombre \(n\) d’étages : \(N=2^n-1\) .

Figure 3. Page de titre du livret « Jeux scientifiques n° 3 » : La Tour d’Hanoï.

Pour une tour de \(8\) étages, on a \(2^8 – 1 = 255\) déplacements. Pour une tour de \(64\) étages, on a un nombre de manœuvres égal à \(2^{64} – 1\) , c’est un nombre de \(20\) chiffres. Cette valeur étant fastidieuse à calculer au XIXe siècle, Lucas donne un moyen pour connaître le nombre de chiffres du résultat : \(\text{E}\left(\log(2^{64})\right)+1\) , où \(\text{E}(x)\) désigne la partie entière de \(x\) . Dans le même fascicule, il justifie mathématiquement la formule proposée pour le nombre de déplacements de la Tour d’Hanoï comportant \(3\) tiges et \(n\) disques.

Quel que soit le nombre de disques, le plus grand d’entre eux n’est déplacé qu’une seule fois, mais le reste de la tour doit changer deux fois de tige, la première fois pour libérer le disque le plus bas et la seconde pour le recouvrir sur une autre tige. Ainsi, la totalité des déplacements, pour une tour de \(n\) disques est toujours égale à la somme de \(1\) déplacement (celui du grand disque) et de deux fois le nombre de déplacements correspondants à une tour de \(n – 1\) disques. Par exemple pour \(4\) disques, on a les trois plus petits à déplacer ( \(7\) coups), puis le plus grand disque ( \(1\) coup), puis une seconde fois les trois plus petits ( \(7\) coups). On a donc \(N_4 = 7 + 1 + 7 = 15\) déplacements. Ainsi \(N_n = N_{n-1} + 1 + N_{n-1} = 1 + 2N_{n-1}\) . Cette relation permet d’initier une suite récurrente dont la conclusion permettra d’établir une relation mathématique pour calculer directement le nombre de coups à effectuer pour déplacer \(n\) disques d’une tige à une autre : \(N_n = 2^n- 1\) .

Codage binaire et ternaire des déplacements

Le déplacement des disques suit inéluctablement un protocole précis qui fut décrit dès 1884 par le petit-neveu d’Édouard Lucas, Raoul Olive : «Pour monter la tour sur trois tiges, quel que soit le nombre d’étages, il faut faire continuellement tourner le disque le plus petit, toujours dans le même sens de rotation circulaire tous les deux coups» . En respectant ce protocole, la suite des déplacements peut être exprimée par une suite de nombres binaires dont le nombre de chiffres est égal au nombre de disques. La suite des nombres binaires qui correspond à celle des décimaux est appelée code binaire naturel.

Figure 4. Code décimal, code binaire naturel. Le binaire naturel est un code pondéré, par exemple : \(6 = 0(2^0) + 1(2^1) + 1(2^2)\) .

Mais on peut organiser une suite de nombres binaires de plusieurs manières dont l’une d’elles, appelée code binaire réfléchi, est caractérisée par ses propriétés d’adjacence : quand on passe d’un nombre au suivant, un seul chiffre binaire change ( \(0\) en \(1\) ou \(1\) en \(0\) ). Cette propriété fut mise à profit en 1872 par un clerc de notaire lyonnais du nom de Louis Gros pour modéliser le fonctionnement du baguenaudier, un autre casse-tête beaucoup plus ancien. Près d’un siècle plus tard, en 1947, un ingénieur américain, Frank Gray, a utilisé ce même code dans un brevet d’invention où il décrit un système capable de transmettre des informations par impulsions électriques pour le compte de la société Bell Telephone Laboratories. Le code binaire réfléchi est connu depuis cette époque sous le nom de code de Gray [4]  .

Figure 5. Code binaire réfléchi (dit code de Gray).

Figure 6. Graphe montrant une propriété du code de Gray : un seul bit (binary digit) change d’état quand on passe d’un sommet à un des trois adjacents, par exemple : de 000 à un des trois sommets 001, 010 ou 100.

Le code de Gray a un intérêt dans de nombreux domaines y compris dans les jeux, en particulier pour modéliser les déplacements des disques de la Tour d’Hanoï. Les déplacements des disques correspondent à une succession de nombres binaires. Considérons une tour à trois disques ( \(\mathsf{d0}\) pour le plus petit, \(\mathsf{d1}\) pour le moyen et \(\mathsf{d2}\) pour le plus grand), et trois tiges ( \(\mathsf{A}\) , \(\mathsf{B}\) , \(\mathsf{C}\) ).

Au départ, les disques sont sur la tige \(\mathsf{A}\) . Sur la figure  7 on montre la succession des sept déplacements à partir de la situation codée \(000\) . Le premier déplacement consiste à transposer le disque \(\mathsf{d0}\) de la tige \(\mathsf{A}\) vers la tige \(\mathsf{B}\) . Cette nouvelle situation est alors codée \(001\) . En effet, seul le disque \(\mathsf{d0}\) a changé de position. La succession des coups pour déplacer la tour d’une tige à une autre revient à écrire le code de Gray quel que soit le nombre de disques.

Le plus petit disque se déplace une fois sur deux, toujours dans le même sens, et les autres sont mis sur la seule tige disponible permettant de ne jamais recouvrir un disque plus petit. En partant de la tige \(\mathsf{A}\) , pour un nombre impair de disques ( \(3\) dans ce cas), si le cycle du petit disque est \(\mathsf{A}\) – \(\mathsf{B}\) – \(\mathsf{C}\) – \(\mathsf{A}\) – \(\mathsf{B}\) alors la position finale de la tour sera la tige \(\mathsf{B}\) ; en partant en sens inverse, \(\mathsf{A}\) – \(\mathsf{C}\) – \(\mathsf{B}\) – \(\mathsf{A}\) – \(\mathsf{C}\) , la tour sera transposée en \(\mathsf{C}\) . Pour un nombre pair de disques le scénario est inversé.

Figure 7 . Codage binaire réfléchi du déplacement des disques pour une tour 3 disques–3 tiges. Le graphe en bas à droite montre le cycle hamiltonien du déplacement des disques ↩ .

La plupart des nombreuses publications au sujet de la Tour d’Hanoï sont des approches mathématiques ; par exemple, les deux articles publiés dans la revue Pour la science , par Jean Lefort  [5] en 2008, et Jean-Paul Delahaye  [6] en 2015, modélisent les déplacements des disques par un graphe, ce qui permet d’indiquer clairement tous les déplacements possibles quelle que soit la phase de jeu. Ils soulignent aussi la correspondance entre la Tour d’Hanoï et les structures fractales. Par exemple, sur la figure 8 , les trois graphes montrent les positions pour trois types de tour avec un disque (I), deux disques (II) ou trois disques (III). Pour trois disques, les sommets du triangle correspondent aux positions des disques de départ ou à l’arrivée : \(\mathsf{AAA}\) si les trois disques sont sur la tige \(\mathsf{A}\) ; \(\mathsf{BBB}\) s’ils sont sur la tige \(\mathsf{B}\) ; \(\mathsf{CCC}\) , sur la tige \(\mathsf{C}\) . Le caractère de droite du code à chacun des sommets indique toujours où se trouve le petit disque \(\mathsf{d0}\) , le caractère central indique la position \(\mathsf{d1}\) , et le caractère de gauche donne la position \(\mathsf{d2}\) , c’est-à-dire du grand disque.

Quelques exemples de déplacements :

\(\mathsf{AAA}\) , les trois disques sont sur la tige \(\mathsf{A}\) ;

\(\mathsf{AAA}\) vers \(\mathsf{AAB}\) , \(\mathsf{d0}\) passe de la tige \(\mathsf{A}\) à la tige \(\mathsf{B}\) ;

\(\mathsf{AAB}\) vers \(\mathsf{ACB}\) , \(\mathsf{d1}\) passe de la tige \(\mathsf{A}\) à la tige \(\mathsf{C}\) ;

\(\mathsf{ACB}\) vers \(\mathsf{ACC}\) , \(\mathsf{d0}\) passe de la tige \(\mathsf{B}\) à la tige \(\mathsf{C}\) .

Deux disques sont alors sur la tige \(\mathsf{C}\) , etc. jusqu’à \(\mathsf{BBB}\) .

Ces graphes indiquent toutes les possibilités pour déplacer la tour d’une tige à une autre. Les plus courts chemins suivent les côtés du triangle. En partant de la tige \(\mathsf{A}\) sur laquelle on a les trois disques \(\mathsf{AAA}\) , si on part à gauche on arrive sur le sommet \(\mathsf{AAB}\) (c’est-à-dire que le petit disque est sur la tige \(\mathsf{B}\) et les autres restent sur la tige  \(\mathsf{A}\) ), si on part à droite on arrive sur le sommet \(\mathsf{AAC}\) (alors le petit disque est sur la tige \(\mathsf{C}\) , et les autres sont restés sur la tige \(\mathsf{A}\) ). En partant du sommet \(\mathsf{AAA}\) on peut aller en \(\mathsf{AAC}\) , puis en \(\mathsf{AAB}\) , etc.

Figure 8. Différents graphes de déplacements. Graphes relatifs aux déplacements pour une tour : un disque (I) ; deux disques (II) ; trois disques (III). Sur ces graphes, le codage des sommets est ternaire. ↩

Par exemple de \(\mathsf{AAA}\) en \(\mathsf{BBB}\) , on peut suivre les sommets \(\mathsf{AAA}\) – \(\mathsf{AAC}\) – \(\mathsf{ABC}\) – \(\mathsf{ABB}\) – \(\mathsf{CBB}\) – \(\mathsf{CBC}\) – \(\mathsf{CAC}\) – \(\mathsf{CAA}\) – \(\mathsf{BAA}\) – \(\mathsf{BAC}\) – \(\mathsf{BBC}\) – \(\mathsf{BBB}\) ; les règles de déplacement sont respectées, mais le chemin suivi n’est pas le plus court. À partir de ces graphes, on voit la naissance d’une structure fractale qui se préciserait en augmentant le nombre de disques.

• Michel Boutin. « Les jeux dans les collections du Conservatoire national des arts et métiers de Paris, 4–La Tour d’Hanoï et le baguenaudier ». In : Le Vieux papier n° 431 (janvier 2019). Planches en couleur IX et X, pp. 25-26. ↩
• Michel Boutin. « Les jeux dans les collections du Conservatoire national des arts et métiers de Paris, 1–Le Jeu icosien (1859) ». In : Le Vieux papier n° 428 (avril 2018). Planche couleur I, pp. 433-441. ↩
• Édouard Lucas. La Tour d’Hanoï, jeu tombé de Saturne. Ce fascicule est le troisième numéro de la collection des « jeux scientifiques » qui en contient six ; tous édités à l’occasion de l’exposition universelle de 1889. Chambon & Baye et Édouard Lucas, Paris, 1889. ↩
• François Sauvageot. « Quadrature ». In : Au fil des maths n° 528 (avril-juin 2018), pp. 55-62. ↩
• Jean Lefort. « La tour de Hanoï, des jeux d’esprit pour la science ». In : Dossier pour la science no 59 (2008), pp. 91-93. ↩
• Jean-Paul Delahaye. « Les tours de Hanoï, plus qu’un jeu d’enfants ». In : Pour la science n° 457 (novembre 2015), pp. 108-114. ↩

Michel Boutin est enseignant en génie électrique à la retraite.

Frédéric de Ligt enseigne les mathématiques au lycée Élie Vinet de Barbezieux.

Cette contribution est extraite d’un article paru dans la revue Le Vieux papier [1] . ↩︎

Le lecteur averti d’aura reconnu l’anagramme de l’auteur. ↩︎

•  LANGUE FRANÇAISE
•  DICTIONNAIRES BILINGUES
•  TRADUCTEUR
•  CONJUGATEUR
•  ENCYCLOPÉDIE
•  CUISINE
•  FORUM
•  JEUX
•  LIVRES
• Suivez nous:    
• EN ES DE IT

tours de Hanoï

Jeu d'origine chinoise, utilisé par les psychologues et les cogniticiens pour tester et formaliser certaines opérations mentales.

Il est formé de trois bâtons verticaux (tours) sur l'un desquels sont empilés des disques de circonférence décroissant de la base au sommet. Il s'agit de transférer cet empilement d'un bâton à un autre en déplaçant un à un les disques de façon à toujours superposer un disque plus petit sur un plus grand.

Les tours de Hanoï

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

Free JavaScripts provided by The JavaScript Source

Cours de mathématiques

Les tours de hanoï.

Les Tours de Hanoï, (également appelées  Tours de Brahma  ou  Tours de Lucas  en référence à son créateur et mathématicien français Édouard Lucas) sont un jeu mathématique ou puzzle inventé en 1883.

3 bâtonnets  composent le jeu, ainsi que plusieurs  disques  de tailles différentes. Les disques sont enfilés dans des tiges par ordre croissant (formant un petit cône).

But et règle du jeu

Le but du jeu  est de déplacer entièrement la pile initiale sur le dernier bâtonnet.

– Le joueur ne doit bouger qu’ un disque à la fois – Seul un  petit disque  peut être placé  sur un plus gros  disque (un peu comme des poupées russes)

Origine du jeu

La Tour de Hanoï est inspirée à Lucas par l’un de ses amis, le professeur Claus de Siam qui raconte une histoire ayant lieu au cœur du temple Kashi Vishwanath :

Trois aiguilles de diamant, plantées dans une dalle d’airain. […] Sur une de ces aiguilles, Dieu enfila au commencement des siècles, 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 du Brahmâ. 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, 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 pousseur de bois attentif aura relevé quelques similitudes avec l’univers échiquéen : déjà, le nom du temple « Kashi Vishwanath » n’est pas sans rappeler l’ex champion du monde indien Viswanathan Anand. Mais également, les 64 disques d’or qui correspondent (si mes calculs sont bons^^) au nombre de cases d’un échiquier.

Solution des tours de Hanoï

La résolution des Tours de Hanoï n’est pas difficile lorsque l’on connaît l’astuce.

• Si le nombre total de  disques est pair . Alors, il suffit à chaque fois de bouger le plus petit disque vers la  droite , puis de bouger le moyen disque vers la droite, ainsi de suite.
• Si le nombre total de  disques est impair . Alors, il faut bouger le plus petit disque vers la  gauche , puis bouger le moyen disque vers la gauche et recommencer ainsi de suite.

S’il n’y a pas de bâtonnet libres, revenez à l’autre extrémité comme s’il s’agissait d’un cercle. C’est tout !

Dans cet exemple la tour est composée de 6 disques. Les disques se déplaceront donc vers la DROITE. Ainsi le 1er coup déplace le petit disque vers la droite. Le 2e coup déplace le disque moyen vers la droite. Le 3e coup déplace le petit disque vers la droite.

Jouer en ligne sur fr.goobix.com

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.

Towers of Hanoi

Towers of Hanoi Animation

This Towers of Hanoi animation uses the <canvas> element and may not run in older browsers.

This is an animation of the well-known Towers of Hanoi problem, generalised to allow multiple pegs and discs. You can select the number of discs and pegs (within limits).

'Get Solution' button will generate a random solution to the problem from all possible optimal solutions - note that for 3 pegs the solution is unique (and fairly boring). If the total number of moves is too big (currently limited to 512) the number of discs will be reduced to meet the limit. This is just to limit the download size and may be increased later.

Solution shown always moves from peg 1 to peg 2. The total number of moves is displayed, so you can count along if you dont believe it!

Playback speed can be adjusted using the 'Speed Factor' box. 'Show Solution' button will play back the last generated solution, so you can get an action replay by lowering the speed factor and pressing the 'Show Solution' button again,

PS If your browser has a problem with the 3D animation, try selecting 2D.

Apprendre les bases de Python pour réussir en N.S.I.

Tours de Hanoï

Difficulté : moyenne

Les tours de Hanoï est un casse-tête composé de trois tours et une pile de disques rangés du plus grand au plus petit comme sur la photo ci-dessous .

Le but est de déplacer la pile de disques sur la tour de droite en ne déplaçant à chaque fois qu'un seul disque et un disque ne peut pas être posé sur un disque plus petit. Voici une animation de ce qu'il faut faire dans le cas où il y a 4 disques.

On peut aller voir Wikipédia par exemple pour plus d'informations.

Nous allons voir qu'il est très simple de créer un programme récursif qui nous dit quoi faire pour résoudre le problème. Tout d'abord on appelle les tours A, B et C. On appelle n le nombre de disque présents au départ dans la tour A. Pour déplacer tous les disques de la tour A vers la tour C, on peut raisonner comme suit :

• On déplace n-1 disques de A vers la tour B
• On déplace le dernier disque de A vers C
• On déplace les n-1 disques de B vers C

L'astuce ici est de créer une fonction hanoi qui prend 4 paramètres : hanoi(n,debut,inter,fin) où n est le nombre de disques à déplacer, debut est la tour de départ de nos n disques, inter est la tour intermédiaire que l'on peut utiliser pour déplacer et fin est la tour ou doivent se trouver les n disques au final.

Ainsi, au début on va lancer hanoi(n,"A","B","C") mais quand on va vouloir déplacer les n-1 disques de A vers B, on écrira hanoi(n-1,"A","C","B") .

Ecrire cette fonction recursive hanoi(n,debut,inter,fin) de manière à afficher (avec print ) à chaque étape le déplacement à effectuer sous la forme "A B" pour un déplacement de la tour "A" vers la tour "B" par exemple.

Entrée : (n,"A","B","C") où n est un entier.

Sortie : Les instructions à suivre pour déplacer les n disques de la tour "A" à la tour "C" donnée sous la forme "A B" pour signifier un déplacement de A vers B et affiché avec print .

Les bases de Python pour le lycée

Recueil d'exercices pour apprendre python au lycée, apprendre python dans le secondaire, python pour le collège et le lycée. exercices, cours, tp, projets..

The #1 tech hiring platform

• Browse latest submissions
• By Project-Team
• Technical and Research Reports
• White Papers
• Browse Inria Activity Reports
• X2HAL : batch import
• Software : create the Codemeta.json
• Create your IDHAL
• Create your CVHal
• Haltools : create your publication list
• Haltools : data extraction (Inria only)
• Setting the correct affiliation
• Which version should I submit?
• Choosing the right document type
• Highlight your publications
• Link records on HAL
• Umbrhal Inria for accessibility
• Customise your CVHAL
• Create and Customise your collection
• HAL online help
• Haltools online help
• X2HAL online help
• HAL Video Tutorials
• HAL API Documentation
• Add thumbnails
• Author identifiers (idHAL and CV)
• Adding HAL publications to your ORCID account
• Inria and Open Science

Les Tours de Hanoï : un problème classique de récursion

• UPMC - Université Pierre et Marie Curie - Paris 6 (4 place Jussieu - 75005 Paris - France) 93591
• CNRS - Centre National de la Recherche Scientifique : UMR7606 (France) 441569
• Function : Author
• PersonId : 3794
• IdHAL : christian-queinnec
• IdRef : 02824933X

inria Interstices  :  Connect in order to contact the contributor

https://inria.hal.science/hal-01350294

Submitted on : Friday, July 29, 2016-5:45:31 PM

Last modification on : Tuesday, April 11, 2023-3:16:28 PM

Dates and versions

Identifiers.

• HAL Id : hal-01350294 , version 1

Collections

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.

708 - La Tour de Hanoï en tant qu’outil cognitif

• March 14, 2012

En psychologie cognitive, dans le domaine de la résolution de problèmes nous avons deux écoles de pensées principales pour l’explication des processus cognitifs impliqués dans cette activité : d’une part l’approche fonctionnaliste de l’école genevoise qui est considérée comme néo-piagétienne et d’autre part l’approche du traitement de l’information. Cependant lorsque nous recherchons des heuristiques efficaces et ce, même au niveau de la recherche, seule la seconde permet de dépasser les difficultés rencontrées. Aussi, dans cet article, nous n’aborderons notre problématique que via ce biais. Dans l’approche de Newell et Simon, le problème surgit de l’écart qui existe entre un état de fait et un état souhaité. Et l’étude de la résolution de problèmes se ramène à celle de la compréhension. Ce processus intègre diverses connaissances dans une représentation mentale qui intègre l’espace du problème et l’ensemble des méthodes activées par la recherche de la solution. Dans ce cadre nous distinguons généralement trois catégories principales de problèmes : ceux de transformation, ceux d’induction de structure et ceux d’arrangements, même si certains problèmes comme le jeu d’échecs sont mixtes et appartiennent à deux catégories. Par contre la tour de Hanoï est un problème de transformation d’état par excellence. L’avantage de ce problème, c’est que son énoncé est élémentaire même pour des élèves en difficultés et que son espace problème est relativement important. Ainsi il offre un spectre d’étude sur le plan cognitif, suffisamment important pour déceler les heuristiques défaillantes, mais surtout pour étudier les choix méthodologiques des testés. En effet, dans ce problème la solution peut être apportée par l’heuristique de réduction de l’écart au but, l’analyse du résolveur général de problèmes, l’analyse régressive ou encore l’analogie. De cette manière, nous pouvons étudier de façon élémentaire la conception de degrés d’abstraction croissants, le déclenchement de règles d’inférences et la mise en oeuvre de stratégies pratiques. La simplicité de ce problème offre aussi la possibilité d’expliciter le polymorphisme des activités mentales sans nécessiter une grande mémoire qui représente un handicap pour les élèves qui ont une déficience au niveau du quotient intellectuel. Comme toutes les étapes du problème sont visuelles, l’élève peut voir de manière interactive ce qu’il effectue aussi il peut corriger en temps réel un choix de trajectoire inopportun ou erroné. Cela permet aussi à l’enseignant de visualiser toutes les étapes de ce processus sans être obligé d’inférer sur les raisons et les choix de l’élève. Cette description explicite et à la fois minimaliste semble très efficace dans le cadre d’apprentissages initiaux mais aussi dans la mémorisation d’un algorithme de résolution. Enfin si ce problème est effectivement inaccessible par l’élève pour une raison spécifique il peut facilement être modifié et simplifié pour se ramener au problème de la tour de Londres qui permet d’engendrer de nombreuses configurations de sous-problèmes. Par cette nouvelle variante, l’enseignant peut mesurer les progrès de son élève quant à son raisonnement et sa manière d’appréhender diverses contraintes. C’est pour l’ensemble de ces raisons que nous conseillons vivement l’exploitation de ce problème pour des enfants en difficultés.

Caméléon | Ελλάς | Expert | GSR | Lygerismes | Perfection | PI | Télémaques Prosfyges

Abel | Archimède | Camus | Carathéodory | Chomsky | Dostoïevski | Einstein | Fraïssé | Galois | Kornaros | Leibniz | Mozart | Sidis | Vincent | Vinci | Vivaldi | Voltaire | Wittgenstein

Advice | Artsakh | Byzance | Chansons | Chronostratégie | Contes | COVID Stats | Droits de l'Humanité | Échecs | Économie | Éducation | Europe | Free Korea | Génocide | Go | Haïku | Hellénisme | Histoire Intelligente | Holodomor | Hua Tou | Hyperstructures | Innovation | Intelligence | Interprétations | Koan | Mathématiques | Missions Musique | Recours européens | Sahara | Stratégie | Tanka | Théâtre | Topostratégie | Urban Design | Western Armenia | ZEE | Zéolithe | Έξυπνη διατροφή