NOMBRES - Curiosités, théorie et usages Accueil / Dictionnaire / Rubriques / Index / Atlas / Références / Nouveautés ORIENTATION GÉNÉRALE  - M'écrire - Édition du: 24/02/2010
Débutants Binaire	NUMÉRATION				Glossaire Général
	BINAIRE
Index des pages NUMÉRATION >>> INDEX		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

---

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.

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

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. Plus simple, on peut y jouer avec 6 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.

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 ceci 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

---

Suite	Baguenaudier Voyageur de commerce
Voir	Arbre de distribution Chemin eulérien Code binaire Échecs Fractale Intelligence artificielle Logique Marche de l'ivrogne Puissance Calcul
Sites	Tours de Hanoi sur Wikipédia pour compléments sur les méthodes itératives et récursives