NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 17/12/2015

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

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 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: 23  = 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 24  = 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 2n – 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: 2n – 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 25  = 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 1011   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 à 264 – 1.

C'est le même nombre que pour les grains de blé de l'échiquier, soit 1,84 1019 . À raison d'un mouvement par seconde, soit 31 558 000 mouvements par an, il faudra 584 milliards d'années (5,8 1011).

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 1011 / 1,5 1010 = 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

= 2n – 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

= 2i – 1

Ce qu'il faut démonter.

Mk

= 2k – 1

Nous connaissons la formule de récurrence.

Mk

= 2 x Mk-1 + 1

Avec notre hypothèse.

 

= 2 x (2k – 1 – 1) + 1

Calculs.

 

= 2k – 2 + 1

Finalement.

 

= 2k – 1             

 

Tour à quatre tiges

 

*      Le jeu à trois tiges (ou aiguilles) a été inventé en 1883. On sait que la quantité minimale de coups vaut 2N – 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

 

 

 

 

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

Cette page

http://villemin.gerard.free.fr/Wwwgvmm/Numerati/Brahma.htm