Jeu de math : " Les tours de Hanoï"

Les tours de Hanoï Le jeu La légende Analyse et solution Observations Petits problèmes

Le jeu

Véritable casse-tête annamite, ce jeu est composé de trois tours et d'anneaux enfilés sur ces tours.
Ces anneaux doivent obligatoirement être posés les uns sur les autres par taille décroissante.
Les pivots peuvent être disposés comme les sommets d'un triangle.
Le jeu consiste donc à déplacer tous les anneaux placés sur une tour A vers une tour C par exemple, en un minimum de temps.
On ne déplace qu'un anneau à la fois et on ne peut placer un anneau que sur un plus grand que lui.
 

PLEIN ECRAN

La légende D'après RECREATIONS MATHEMATIQUES de E. Lucas, "L'écrivain Asaphad rapporte que Sessa, fils de Daher, imagina le jeu des échecs, où le roi, quoique la pièce la plus importante, ne peut faire un pas sans le secours de ses sujets : les pions, dans le but de rappeler au monarque indien Scheran les principes de justice et d'équité avec lesquels il devait gouverner. Scheran, enchanté d'une leçon donnée d'une manière ingénieuse, promit à l'inventeur de lui donner tout ce qu'il voudrait pour sa récompense.
Celui-ci répondit : 'Que votre Majesté daigne me donner un grain de blé pour la première case de l'échiquier, deux pour la seconde, quatre pour la troisième, et ainsi de suite en doublant jusqu'à la soixante-quatrième case.'
Il aurait fallu huit fois la superficie de la Terre, supposée entièrement ensemencée, pour avoir en une année de quoi satisfaire au désir du modeste bramine. Le nombre des grains de blé est égal au nombre de déplacements de la tour de Hanoï à soixante-quatre étages."
Jan Gullberg (1936, 1998) écrit :"Avec près de 100 grains par centimètre cube, le volume total des grains aurait représenté deux cent kilomètres cubes, dont le chargement aurait nécessité deux mille millions de wagons, soit un train égal à mille fois la circonfétrence de la Terre".

Nous allons voir et calculer approximativement, à raison d'une seconde pour le déplacement d'un anneau, qu'il faut environ cinq milliards de siècles pour déplacer les 64 anneaux. La durée de la vie de la terre n'y suffirait pas ! Il est alors facile de prévoir la fin du monde lorsque les 64 anneaux seront déplacés. Nous calculerons effectivement ce résultat ci-après. Nous allons dans le paragraphe suivant observer les résultats du jeu automatique avec un nombre d'anneaux inférieur ou égal à 12.

Analyse et solution Le jeu est toujours possible et demande deux fois plus de temps chaque fois que l'on ajoute un anneau à la tour initiale. En effet, si l'on sait résoudre le problème pour trois étages (en 7 coups), en transportant les anneaux de la tour A vers la tour B , alors on sait résoudre le problème pour quatre annneaux. Ainsi, on transporte les 3 anneaux de la tour A vers la tour B (7 coups) , puis on déplace le quatrième anneau de la tour A vers la tour C (1 coup) et enfin on transporte les trois anneaux de la tour B vers la tour C (7 coups). Le nombre de coups devient le double, plus un ; ici il est devenu : 7+1+7=15 soit 2x7+1.
Le nombre de coups croît exponentiellement, c'est donc extrêmement rapide.
Ci-dessous, entrer le nombre d'anneaux sur la première tour et régler la vitesse de déplacement des anneaux.

PLEIN ECRAN

Tableau des résultats pour un nombre d'anneaux allant de 1 à 12.

Nombre d'anneaux	1	2	3	4	5	6	7	8	9	10	11	12
Nombre de coups	1 = 21 - 1	3 = 22 - 1	7 = 23 - 1	15 = 24 - 1	31 = 25 - 1	63 = 26 - 1	127 = 27 - 1	255 = 28 - 1	511 = 29 - 1	1023= 210 - 1	2047= 211 - 1	4095= 212 - 1

De façon générale, le nombre de déplacements pour n anneaux est 2ⁿ - 1.

La démonstration se fait très simplement par récurrence.
D'ailleurs ce procédé correspond à la programmation des tours ci-dessus.
-Le résultat est vrai pour n=1.
-Supposons le résultat vrai pour n et montrons qu'il est vrai pour n+1 :
Alors on a 2ⁿ - 1 coups pour n anneaux.
Pour 1anneau de plus, donc pour n+1 anneaux , il faudra 2( 2ⁿ - 1)+1 coups soit 2ⁿ⁺¹ - 2+1 coups, c'est-à-dire 2ⁿ⁺¹ - 1 coups.
C'est bien ce que l'on veut.
-Finalement le résultat est vrai pour 1 anneau ; quand il est vrai pour n anneaux, il est vrai pour n+1 anneaux.
La récurrence est bien démontrée : pour n anneaux, il faut 2ⁿ - 1 coups.

On peut aussi calculer autrement :
appelons C1, C2... Cn les nombres de coups pour1, 2,... n anneaux sur une tour.

C1 =             1 C2 = 2 C1  + 1 C3 = 2 C2  + 1 C4 = 2 C3  + 1 . . Cn-1 = 2 Cn-2   + 1 Cn   = 2 Cn-1  + 1

Multiplions chaque ligne par 2n-1 puis 2n-2 puis... 21 2n-1 C1 =                 2n-1 2n-2 C2 = 2n-1C1   + 2n--2 2n-3 C3 = 2n-2 C2  + 2n--3 2n-4 C4 = 2n-3 C3  + 2n--4 . . 21 Cn-1 = 22 Cn-2   + 21 Cn   = 2 Cn-1  + 1

En ajoutant membre à membre, nous obtenons :
Cn   = 1 + 2¹ + 2² + 2³ + 2¹ + 2⁴ + 2⁵ + ... + 2^n-1.
Nous avons une progression géométrique de n termes, de raison 2 et de premier terme 1.
La somme donne
Cn   = 1 ( 2ⁿ - 1)/(2 - 1)
d'où

Cn   = 2n - 1

Le calcul du résultat de la légende
Prenons le cas n = 64 évoqué dans la légende ci-dessus.
La durée nécessaire à raison d'une seconde par coup est de 2⁶⁴ - 1 secondes.
Evaluons cette durée : nous avons 2^{10 = 1024} ~ 1000, nous arrondirons à 10³ pour simplifier les calculs.
Ainsi 2⁶⁴ - 1 ~ 2⁶⁴ = (2¹⁰)⁶ x 2⁴ ~ 10¹⁸x16
Or une journée de 24 heures a ( 24x3600 = ) 86400 secondes.
Une année de 365 jours a (365x86400 = ) 31 536 000 secondes soit un peu plus de 3 x 10 000 000 secondes ou 3x10⁷ secondes.
Nous trouvons donc à peu près (10¹⁸x16)/( 3x10⁷) années, c'est-à-dire environ (16/3)x10¹¹ années ou un peu plus de 5x10¹¹ années.
Finalement on obtient un peu plus de 5x10⁹ siècles.
Nous retrouvons bien les 5 milliards de siècles de la légende.

Observations Regardons très attentivement les déplacements de chaque anneau lorsqu'on joue dans un temps minimal.
Disposons les tours selon un triangle ABC et alternons les couleurs des anneaux.
Nous notons que :
- Un coup sur deux déplace le plus petit anneau ;
- L'anneau supérieur passe successivement sur chacune des tours en tournant toujours dans le même sens ;
- Un anneau est toujours posé sur un anneau de couleur différente ;
- La suite des déplacements est symétrique ;
- Chaque suite reprend la totalité des mouvements de la suite antérieure selon la disposition S + 1 + S ;
On peut spontanément écrire la suite des déplacements des anneaux dès lors que l'on connaît la suite des déplacements pour 2 ou 3 anneaux.

Voici de gauche à droite les anneaux à déplacer quand on dispose de 1 à 4 anneaux.

Voici comment tournent 4 anneaux sur des tours disposées triangulairement. Chaque anneau tourne toujours dans le même sens. Ici les verts tournent dans un sens et les rouges dans l'autre.


Le plus petit anneau est déplacé 8 fois, le suivant 4 fois, puis l'autre 2 fois et enfin le plus grand est déplacé 1 seule fois.
Un anneau est déplacé deux fois moins souvent que celui qui est de taille immédiatement inférieure.

Nous pouvons organiser les résultats dans un tableau
a1 représente le plus petit anneau ; a2 le suivant et ainsi de suite... nous irons ici jusqu'à 4 anneaux donc jusqu'à a4.
Dans le tableau, nous notons d'abord la suite des anneaux déplacés et enfin à droite du tableau le nombre de déplacements de chacun d'entre eux.

Nombre d'anneaux

Suite des déplacements

a1

a2

a3

a4

1

a1

1

2

a1

a2

a1

2

1

3

a1

a2

a1

a3

a1

a2

a1

4

2

1

4

a1

a2

a1

a3

a1

a2

a1

a4

a1

a2

a1

a3

a1

a2

a1

8

4

2

1

Petits problèmes Les anneaux sont numérotés à partir du plus petit.
1°) Sachant que l'anneau 10 d'une tour a été déplacé 1 seule fois, quel est le nombre d'anneaux que comporte la tour de départ ?
2°) Sachant que l'anneau numéro 3 a été déplacé 32 fois, peut-on préciser le nombre total d'anneaux ?

3°) Partage de segments :
On retrouve les particularités des suites obtenues si on plie en deux une bande de papier.
Prenons une bande de 16 cm de longueur.
On plie en deux et on note 4 sur le pli.
On plie encore en deux et on note 3 sur chaque pli.
On plie encore en deux et on note 2 sur chaque pli.
On recommence encore une fois en notant 1 sur chaque pli.
Nous retrouvons la même suite que celle des anneaux déplacés :
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

4°) Généralisation du problème
Il est possible de généraliser le jeu des tours de Hanoï en augmentant le nombre de tours.
Avec 4 tours :
pour 3 anneaux , 5 coups : 1 2 3 2 1
pour 4 anneaux , 9 coups : 1 2 3 2 4 2 3 2 1
pour 5 anneaux , 13 coups : 1 2 3 2 1 4 5 4 1 2 3 2 1
pour 6 anneaux , 17 coups : 1 2 3 2 1 4 5 4 6 4 5 4 1 2 3 2 1
...
Réponses 1°) 10 anneaux.
2°) L'anneau numéro deux a donc été déplacé 64 fois et le numéro un 128 fois. C'est 2^8-1, il y avait 8 anneaux.

"Pour un homme, il existe un gigaplex de pensées possibles."
(Un gigaplex est le nombre 1 suivi d'un milliard de zéros.)
Rudy Rucker, Infinity and the Mind