NOMBRES – Curiosités, Théorie et Usages Accueil DicoNombre Rubriques Nouveautés Édition du: 02/12/2023 Orientation générale  DicoMot Math Atlas Références M'écrire Barre de recherche DicoCulture Index alphabétique Brèves de Maths
	NUMÉRATION
Débutants Binaire	BINAIRE			Glossaire Général
INDEX Bases de numération	Code Gray	Tour de Hanoi	Baguenaudier
		Sommaire de cette page >>> Tour de Hanoi >>> Principe: 2 anneaux >>> Solution: 3 anneaux >>> Explication: 4 anneaux >>> Théorie >>> Vérification: 5 anneaux >>> Tour de Brahmâ: 64 anneaux >>> Tour bicolore >>> Culture >>> Compter les mouvements (récursivité) >>> Tour à quatre tiges >>> Tour de Stockmeyer

Tour de Hanoi ou de Brahmâ

ou tours de Hanoi

Casse-tête classique dont la résolution suit en fait le principe du codage Gros-Gray: changer un seul élément à la fois. Même principe de résolution que le baguenaudier.

Tour de Brahmâ: objet d'un culte religieux Hindouiste.

Intérêt: excellent exemple de procédure récursive, régal des programmeurs.

TOUR DE HANOI

Jeu créé en 1883 par le français Édouard Lucas (1842-1891). Il s'agit de la tour de Brahmâ de 64 disques simplifiée à 8 disques. Il faut 28 – 1 = 255 coups pour le terminer. Lucas en fait un petit livre au titre plein de mystère en 1882: La tour de Hanoï Véritable casse-tête annamite Jeu rapporté du Tonkin par le professeur N. Claus (de Siam) du collège Mandarin Li-Sou-Stian Claus est une anagramme de Lucas et Li-Sou-Tina de Saint Louis. Il commence son ouvrage par: D'après une vieille légende indienne, les brahmes se succèdent depuis bien longtemps sur les marches de l'autel dans le temple de Bénarès pour exécuter le déplacement de la Tour Sacré de BRAHMA aux soixante-quatre étages en or fin, garnis de diamants de Golconde. Quand tout sera fini, la tour et les brahmes tomberont, et ce sera la fin du monde! Le jeu original de Lucas est conservé au Conservatoire des Arts et métiers à Paris. Plus simple, on peut y jouer avec des pièces de monnaies de tailles différentes. Ou encore plus simple pour enfants, avec trois anneaux pris dans un jeu de bébés. Des rondelles de cartons peuvent très bien faire l'affaire également.

PRINCIPE avec deux anneaux
Avec trois supports à notre disposition, il faut faire passer les anneaux de gauche à droite, sans que jamais un plus grand soit sur un plus petit. Règle générale Déplacer un à un 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 cela en un minimum de coups et sans qu'un plus gros disque soit posé sur un plus petit.
Position de départ On note 2 l'anneau du bas et 1 celui du haut. On symbolise la situation de départ par trois nombres comme indiqué: 21 0 0 Étape 1 On déplace l'anneau 1 de gauche vers le milieu On symbolise de cette façon: 2 1 0 Étape 2 L'anneau 2 passe de gauche à droite: 0 1 2 Étape 3 Le petit anneau se place à gauche sur le plus grand: 0 0 21

Solution avec trois anneaux
Avec notre notation, voici les mouvements. La résolution exige sept mouvements à partir de la position de départ. Soit 8 positions au total. En fait: 2^3 = 8	321 32 3 3 0 1 1 0	0 0 2 21 21 2 0 0	0 1 1 0 3 3 32 321

Explication avec quatre anneaux
Solution en 2^4 = 16 mouvements. On analyse le mouvement du 1, puis celui des autres chiffres.
Déplacement du 1 (petit anneau)	4321 432 43 43 4 41	0 1 1 0 3 3	0 0 2 21 21 2	Descente droite Immobile Descente droite Immobile Descente droite circulaire: le 1 passe de l'autre côté
Déplacement des autres chiffres (autres anneaux)	41 41 4 0 0 2 21 21 2 0 0	3 32 321 321 32 3 3 0 1 1 0	2 0 0 4 41 41 4 43 43 432 4321	Le 2 est déplacé, c'est la seule possibilité. Le 4 est déplacé, c'est la seule possibilité. Le 2 est déplacé, c'est la seule possibilité. Etc.

Théorie

La règle est simple: Le 1 descend toujours d'un cran vers la droite, avec effet circulaire le cas échéant. Le mouvement du 1 se produit une fois sur deux. Dans les autres cas, le seul chiffre qui peut bouger fait mouvement. La résolution exige 2^n – 1 mouvements, si n est la quantité d'anneaux. Voir Échiquier et les grains de blé Note Récemment, des mathématiciens ont prouvé que, quel que soit le nombre de disques, les déplacements ne se répètent jamais consécutivement dans le même ordre: jamais 2 fois de suite AB ou AB, AC, etc. Commentaires Édouard Lucas a montré qu'il y toujours une solution et que le nombre de mouvements est: 2^n – 1. La méthode exposée ci-dessus est dite itérative. Il existe une méthode plus expéditive dite récursive. Elle est très utilisée pour illustrer la méthode récursive de résolution des problèmes par programmation de type déclaratif.

Vérification avec cinq anneaux
Solution en 2^5 = 32 mouvements. Première partie pour dégager le 5: 16 mouvements.	54321 5432 543 543 54 541 541 54 5 5 52 521 521 52 5 5	0 1 1 0 3 3 32 321 321 32 3 3 0 1 1 0	0 0 2 21 21 2 0 0 4 41 41 4 43 43 432 4321
Deuxième partie assez symétrique à la première: 16 mouvements. Pour être puriste, il faudrait, ici, inverser colonne milieu et colonne de droite pour retrouver la configuration désirée à droite. Alors il faudrait changer les règles en conséquence lorsque la quantité d'anneau est impaire.	0 1 1 0 3 3 32 321 321 32 3 3 0 1 1 0	5 5 52 521 521 52 5 5 54 541 541 54 543 543 5432 54321	4321 432 43 43 4 41 41 4 0 0 2 21 21 2 0 0

TOUR DE BRAHMÂ

5,8 10^11 Nombre d'années pour terminer la tour de Brahmâ. Calcul Pour les 64 disques de la tour de Brahmâ, on montre que le nombre minimum de mouvements est égal à 2^64 – 1. C'est le même nombre que pour les grains de blé de l'échiquier, soit 1,84 10^19 . À raison d'un mouvement par seconde, soit 31 558 000 mouvements par an, il faudra 584 milliards d'années (5,8 10^11). Soit 42,6 fois plus que l'âge de l'Univers estimé à 13,7 milliards d'années. Or, selon cette légende indienne, l'Univers a, à peine, vécu et il lui reste encore quelques années à vivre! (5,8 10^11 / 1,5 10^10 = 38 fois l'âge de l'Univers). Légende Dans le grand temple de Bénarès, sous le dôme qui marque le centre du monde, repose un socle de cuivre équipé de trois aiguilles verticales en diamant de 50 cm de haut. À la création, Dieu enfila 64 plateaux en or pur sur une des aiguilles, le plus grand en bas et les autres de plus en plus petits. C'est la tour de Brahmâ. Les moines doivent continûment déplacer les disques de manière que ceux-ci se retrouvent dans la même configuration sur une autre aiguille. La règle de Brahmâ est simple: un seul disque à la fois et jamais un grand plateau sur un plus petit. Arrivé à ce résultat, le monde tombera en poussière et disparaîtra.

Voir Âge de l'Univers

Tour bicolore
Trois pieux; deux jeux d'anneaux de deux couleurs. Même règle que ci-dessus, en admettant que l'on peut poser un anneau sur un de même taille. Solution Ici, en 29 coups, sans doute la solution optimale: AC - BC - AB - CB - CB - AC - BA - BA - BC - BC - AC - AC - BA - CA - CA - CB - CB - AC - AC - BA - BA - CA - CA - CB - AC - AC - AB - CB - CA.

CULTURE

Hanoi, la "ville au-delà du fleuve", capitale du Viêt Nam. Au Tonkin, sur le delta du fleuve Rouge. Deuxième ville du pays après Hô-Chi-Minh-Ville. Prise par les Français, la ville devint la capitale du protectorat du Tonkin puis, après 1887, le siège du gouvernement de l'Indochine française. Le 19 mars 1946, le massacre de Français marqua le début de la guerre d'Indochine. Devenue la capitale du Viêt Nam du Nord en 1954, elle fut choisie comme capitale du Viêt Nam réunifié en 1975. Brahmâ: un des principaux dieux du panthéon hindou, premier créé et créateur de toute chose. Il est souvent représenté avec quatre bras et quatre têtes qui symbolisent son omniscience et son omniprésence.

Voir DicoCulture

Compter les mouvements
De manière récursive, la résolution de la tour de Hanoi se réduit à ces trois règles: Faire passer n – 1 disques supérieurs de du support 1 au support 2. Déplacer le nième disque, le plus grand, du support 1 au support 3. Faire passer n – 1 disques du support 2 au support 3, sur le nième disque. Résumé en formule Si M est la quantité de mouvements à effectuer M1 = 1 Mn = 2 x Mn-1 + 1	Si on sait faire cette opération, on sait les faire toutes.
On démontre par récurrence forte que:	Mn	= 2^n – 1
Point de départ.	M1	= 2 – 1 = 1 C'est vrai
Hypothèse de récurrence: relation vraie pour tous les entiers i jusqu'à k.	Mi	= 2^i – 1
Ce qu'il faut démonter.	Mk	= 2^k – 1
Nous connaissons la formule de récurrence.	Mk	= 2 x Mk-1 + 1
Avec notre hypothèse.		= 2 x (2^k – 1 – 1) + 1
Calculs.		= 2^k – 2 + 1
Finalement.		= 2^k – 1

Tour à quatre tiges
Le jeu à trois tiges (ou aiguilles) a été inventé en 1883. On sait que la quantité minimale de coups vaut 2^N – 1 où N est la quantité de disques à déplacer. En 1908, Henri Dudeney propose la variante à quatre tiges et il donne une formule indiquant le nombre de coup pour la résoudre.	En 2014, Thierry Bousch, université d'Orsay, démontre que la formule de Dudeney est bien la formule minimale. Spécialiste des systèmes dynamiques, sa méthode est originale. Il construit des chemins dans le graphe des possibilités. Il analyse des systèmes perturbés: sur la tige initiale, il manque des disques sans que l'on sache lesquels…
La formule de Dudeney donnant la quantité de mouvements pour N disques sur quatre tiges:	avec delta n, la racine triangulaire par défaut de n, c'est-à-dire le plus grand entier p tel que:

Anglais: four-peg variant of the Towers of Hanoi

Tour de Stockmeyer
Présentation Similaire à la tour de Hanoï à quatre tiges, mais la quatrième est centrale, et elle sert de pivot aux mouvements: une pièce ne peut être déplacée que vers la tige centrale ou de la tige centrale vers une des trois tiges périphériques.	Le jeu Source image: La tour de Stockmeyer – Maths-en-Jeans
Quantité de mouvements La solution minimale avec quatre disques exige vingt mouvements. Avec cinq disques, il en faut au minimum trente-deux. Historique C'est en 1994 que Paul Stockmeyer propose cette variante de la tour de Hanoï. Il a conjecturé, comme E. Dudeney, que la quantité minimale de mouvements est le double de la somme des nombre 3-friables. La preuve en a été apportée en 2017 par Thierry Boush.	Nombres 3-friables La quantité de mouvements pour k disques est égale au double de la somme des k plus petits nombres 3-friables. Ces nombres sont de la forme 2^a٠3^b. Ces sont 1, 2, 3, 4, 6, 8, 9, 12 … dont la double-somme pour k = 4 est 20, et celle pour k = 5 est 32.

Anglais: In 1994, Paul Stockmeyer proposed a four-peg variant of the Tower of Hanoi puzzle

Voir Brève 56-1101

Solution de la tour de Stockmeyer

Illustration présente en Les entiers friables – Jean-Paul Delahaye – Pour la Science N539 septembre 2022

Suite	Baguenaudier Voyageur de commerce
Voir	Arbre de distribution Chemin eulérien Code binaire Cylindre Échecs	Fractale Intelligence artificielle Logique Marche de l'ivrogne Puissance Calcul
Livre	Les tours de Hanoï, plus qu'un jeu d'enfants – Jean-Paul Delahaye – Pour la Science Novembre 2015 Ce livre de 2013 est en lecture gratuite sur Internet pour certaines pages (illustration)
Sites	Tours de Hanoi sur Wikipédia pour compléments sur les méthodes itératives et récursives La quatrième tour de Hanoï – Thierry Boush – 2014 Récursion - Tours de Hanoï – Christian Queinnec – Vidéo La tour de Stockmeyer – Thierry Boush – Paris-Saclay OEIS A341579 - Number of steps needed to solve the Towers of Hanoi exchanging disks puzzle with 3 pegs and n disks OEIS A160002 – Number of moves needed to solve 4-peg Tower of Hanoi Puzzle with n disks.
Cette page	http://villemin.gerard.free.fr/Wwwgvmm/Numerati/Brahma.htm