Accueil

Les Tours de Hanoi

G.Gershwin Rapsody in Blue

 
  Les Tours de Hanoi sont une récréation mathématique classique, publiée en 1883 par Edouard Lucas, mathématicien spécialiste de la théorie des nombres, connu pour ses travaux sur les suites récurrentes dont la suite de Fibonacci et la suite de Lucas qui lui est associée.
  Selon la légende imaginée par E. Lucas, la fin du monde surviendra lorsque les moines d’un monastère indien auront terminé le transfert de  64 disques d’or en respectant les règles ci dessous.

REGLES DU JEU


  On dispose de 3 tiges. Sur la première sont enfilés des disques percés, de diamètres décroissants, les deux autres sont libres. Le problème consiste à transférer tous ces disques sur l’une des deux autres tiges, en respectant 3 règles :

  1. déplacer les disques un à un
  2. déposer les disques seulement sur les tiges
  3. ne jamais poser un disque sur un disque de diamètre inférieur

  Commencez avec quelques pièces de monnaie de diamètres différents, par exemple : 0.01, 0.02, 0.10, 0.20 et 0.50 € . Tant que la colonne se limite à 2 ou 3 pièces : aucune difficulté, mais à partir de 4 pièces vous devrez agir méthodiquement pour éviter les fausses manœuvres.

  Comme le recommande Descartes dans son Discours sur la Méthode :
"... diviser chacune des difficultés que j'examinerois, en autant de parcelles qu'il se pourroit,...".
 - nous débuterons donc avec un exemple simple
 - puis nous compliquerons progressivement le problème
 - étape par étape nous nous approcherons de la solution. 


1er exemple

- Prenons le cas le plus simple : 1 seul disque !

  Enfantin, mais ... indispensable pour comprendre la suite.
  Pour transférer le seul disque d’une colonne de 1 disque

1 seule opération suffit

nous écrirons en abrégé :

U1 = 1

que nous lirons :
« U indice 1 égal 1 »
( sous-entendu 1 disque à déplacer nécessite 1 opération )


2ème exemple

- Compliquons très légèrement le problème et déplaçons une colonne de 2 disques.

Le transfert demandera 3 opérations représentées sur la figure suivante :

  • j’ai pris le petit disque supérieur et l’ai enfilé sur la 2ème tige 
  • j’ai pris le grand disque inférieur et l’ai enfilé sur la 3ème tige 
  • enfin j’ai repris le petit disque et l’ai déposé sur le grand.

Autrement dit :

  • transfert de 1 disque, comme dans le cas précédent : 1 opération
  • déplacement du disque inférieur supplémentaire : 1opération
  • nouveau transfert de 1 disque, comme précédemment : 1 opération.

Total : 3 opérations

U2= 3

que nous lirons « U indice 2 égal 3 », (sous-entendu 2 disques à déplacer nécessitent 3 opérations )


3 ème exemple

- Passons maintenant à 3 disques

décomposons les opérations en trois stades déjà rencontrés :

-1- Déplacement des 2 disques supérieurs sur la 3ème tige

qui, comme nous le savons, demande   U2 opérations

-2- Puis, déplacement du disque supplémentaire par rapport à l'exemple précédent

1 opération

-3- Enfin déplacement des 2 disques de 3ème tige vers la 2ème

nécessitant à nouveau :

U2 opérations

Soit, en tout, pour les 3 étapes :

U3 = U2 + 1 + U2
U3 = 2 U2 + 1

c’est à dire :  2 fois 3 plus 1

U3 = 7 opérations


4 ème exemple

- Pour 4 disques, nous nous passerons du dessin.

Les 3 étapes seront décomposées comme toujours :
- 1 - déplacement des 3 disques supérieurs sur la 2ème tige : U3
- 2 - déplacement du disque inférieur sur la 3ème tige : 1 opération
- 3 - déplacement des 3 disques de 2ème tige vers la 3ème:U3

Soit, en tout, pour déplacer les 4 disques :

U4 = U3 + 1 + U3
U4 = 2 U3+ 1

d'où : 2 fois 7 plus 1

U4 = 15 opérations


5 ème exemple -

Pour 5 disques il faudra, selon le même principe :

U5 = U4 + 1 + U4
U5 = 2U4 + 1
U5 = 31 opérations


 Pour résumer :

 U1 = 1
U2 = 2U1 + 1
U3 = 2U2 + 1
U4= 2U3 + 1
U5= 2U4 + 1

qui correspond à une suite de nombres dans laquelle un nombre vaut toujours le double du précédent plus 1

{U1, U2, U3, U4, U5 ...} c’est à dire {1, 3, 7, 15, 31,...}

formant une suite récurrente, que l’on pourra étendre aussi loin que l'on veut, en appliquant la règle de récurrence :

Un = 2Un-1 + 1

n est un nombre entier positif, représentant le nombre de disques.

  Ou encore sous la forme :

Un+1 = 2Un+ 1

Application :

  Quel est le nombre minimum d'opération nécessaire au transfert d'une colonne de 10 disques

  Ce nombre sera calculé de proche en proche pour des colonnes de tailles croissantes :

Nombre
de disques

 Opération

Nombre
d'opérations

0   0
1 2 x 0 + 1  1
2 2 x 1 + 1  3
3 2 x 3 + 1  7
4 2 x 7 + 1  15
5 2 x 15 + 1  31
6 2 x 31 + 1  63
7 2 x 63 + 1  127
8 2 x 127 + 1  255
9 2 x 255 + 1  511
10 2 x 511 + 1  1023

  Par ce procédé il aura fallu calculer tous les termes inférieurs avant d’arriver au dixième qui seul nous intéresse :
existe-t-il une méthode donnant directement un terme sans devoir calculer tous les précédents ?


Rappel sur la notion de "Puissance"

  Pour multiplier plusieurs fois un nombre par lui même ( pour calculer de la surface d'un carré ou le volume d'un cube), on utilise une écriture abrégée :

  2*2 s’écrit plutôt 22 qui se lit « deux au carré » ou « deux puissance deux »
  2*2*2 s’écrit 23 qui se lit « deux au cube » ou « deux puissance trois »
  2*2*2 s’écrit 24 qui se lit « deux puissance quatre »
  ….
  2*2*2…*2 (n fois) s’écrit 2n qui se lit « deux puissance n »

  Le petit chiffre placé en haut à droite, appelé exposant, indique le nombre de fois que l’on doit multiplier 2 par lui-même.

  Sachant cela, multiplions plusieurs fois 2 par lui-même et notons les résultats successifs.

21 2
22 4
23 8
24 16
25 32
26 64
27 128
28 256

  On remarque immédiatement que :

U2 = 22 – 1
U3 = 23 – 1
U4 = 24 – 1

et donc la formule générale :

Un = 2n – 1

  Ce qui reste à démontrer. En effet, une loi vérifiée sur un nombre limité d’exemples particuliers ne sera admise comme règle générale, qu’après une démonstration mathématique rigoureuse.

  Supposons que cette relation soit vraie pour n, restera-t-elle vraie pour n+1 ? Reprenons pour cela la règle de récurrence précédemment établie :

Un+1= 2Un+ 1

et remplaçons Un par (2n – 1)

Un+1 = 2(2n – 1 ) + 1
Un+1= 2*2n – 2+ 1
Un+1= 2n+1 – 1

  Nous retrouvons notre formule générale, appliquée au terme (n+1).

  Nous avons donc démontré que : si la formule est vraie pour une valeur quelconque de n elle sera également vraie pour la suivante.

  Mais nous savons aussi qu’elle est vraie pour n=1  puisqu'il suffit d'une opération pour transférer 1 disque et 3 pour en déplacer 2.
  Elle sera donc vraie pour la valeur suivante de n : 2 disques
  … et ainsi de suite pour toutes les valeurs possibles de n.

  Cette méthode est appelée démonstration par récurrence


Méthode pratique de résolution

  Reste à définir l’astuce qui permettra de jouer sans risque d’erreur, pour faciliter les opérations les disques de rangs impairs sont colorés en rouges, ceux de rangs pairs en bleus.
  Pour opérer sans erreur :
  • un disque rouge sera déplacé d’une tige vers la droite :
    • de la 1 ère à la 2ème tige
    • de la 2ème à la 3ème
    • de la 3ème à la 1ère ( à défaut de 4ème tige, c’est à dire 2 tiges à gauche )
  • un disque bleu sera déplacé d’une tige vers la gauche :
    • de la 1ère à la 3ème tige (faute de tige zéro et donc 2 tiges à droite)
    • de la 2ème à la 1ère
    • de la 3ème à la 2ème
    • on ne reprend jamais un disque que l’on vient de poser
    • on ne prends jamais le plus grand des 3 disques supérieurs 

  Les opérations pour le déplacement d'une colonne de 5 disques sont représentées dans le tableau suivant. 
   Conformément aux règles ci-dessus :

  • les disques de rang impair sont déplacés, si possible d'un rang vers la droite , sinon de 2 rangs vers la gauche

  • ceux de rang pair sont déplacés d'un rang vers la gauche ou de 2 rangs vers la droite en cas d'impossibilité.

   Dans le tableau suivant, on remarquera que :

  • le disque 1 reste 2 lignes de suite sur la même tige ( il est joué 1 fois sur 2 )

  • le disque 2 reste 4 lignes de suite sur la même tige ( il est joué 1 fois sur 4 )

  • le disque 3 reste 8 lignes de suite sur la même tige ( il est joué 1 fois sur 8 )

Etape Tige A Tige B Tige C

Commentaire

0

12345

 

 

 Je prends 1, il est impair : je le pose sur une tige à droite

1

2345

1

 

 Je prends 2, il est pair : je le pose 2 tiges à droite

2

345

1

2

 3 ne peut être posé : je prends 1 et le pose 1 tige à droite

3

345

 

12

 3 est devenu jouable, il est impair : je le pose 1 tige à droite

4

45

3

12

 Seul 1 est jouable : faute de place à droite, 2 tiges à gauche

5

145

3

2

 Je reprends 2, étant pair, il est déplacé d'une tige à gauche

6

145

23

   

 Je déplace1 ...

7

45

123

    

pour terminer la mini tour 123 en B.

8

5

123

4

 J'attaque la tour 1234 en C

9

5

23

14

en préparant la reconstruction de 123 sur 4

10

25

3

14

 

11

125

3

4

 

12

125

 

34

 

13

25

1

34

 

14

5

1

234

 

15

5

 

1234

La mini-tour 1234 est terminée

16

 

5

1234

 

17

1

5

234

 

18

1

25

34

 

19

 

125

34

 

20

3

125

4

 

21

3

25

14

 

22

23

5

14

 

23

123

5

4

 

24

123

45

 

 

25

23

145

 

 

26

3

145

2

 

27

3

45

12

 

28

 

345

12

 

29

1

345

2

 

30

1

2345

 

 

31

 

12345

 

Terminé en 31 coups !

   En opérant rapidement, disons une seconde pour prélever un disque et une autre pour le reposer, le transfert de ces 5 disques demandera environ 1 minute.

  Revenons à nos moines : quand auront-ils terminé le déplacement des 64 disques en maintenant une cadence d'un déplacement par seconde ?
  Que vaut Un pour n = 64 ? 

  Autrement dit, quel est le 64eme terme de la suite { 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024,  ... }  ?

  C'est un nombre de 20 chiffres commençant par  18 446 744 073 709 6 ..., il vous reste à convertir ces secondes en milliards de siècles !


Extraire la page pour l'enregistrer ou l'imprimer