|
Les
tours de Hanoï
 |
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
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.
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.
Tableau des résultats pour un nombre d'anneaux allant de 1 à 12.
d'anneaux
de coups
21 - 1
22 - 1
23 - 1
24 - 1
25 - 1
26 - 1
27 - 1
28 - 1
29 - 1
210 - 1
211 - 1
212 - 1De façon générale, le nombre de déplacements pour n anneaux est 2n - 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 2n - 1 coups pour n anneaux.
Pour 1anneau de plus, donc pour n+1 anneaux , il faudra 2( 2n - 1)+1 coups soit 2n+1 - 2+1 coups, c'est-à-dire 2n+1 - 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 2n - 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 + 1Multiplions 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 + 21 + 22 + 23 + 21 + 24 + 25 + ... + 2n-1.
Nous avons une progression géométrique de n termes, de raison 2 et de premier terme 1.
La somme donne
Cn = 1 ( 2n - 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 264 - 1 secondes.
Evaluons cette durée : nous avons 210 = 1024 ~ 1000, nous arrondirons à 103 pour simplifier les calculs.
Ainsi 264 - 1 ~ 264 = (210)6 x 24 ~ 1018x16
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 3x107 secondes.
Nous trouvons donc à peu près (1018x16)/( 3x107) années, c'est-à-dire environ (16/3)x1011 années ou un peu plus de 5x1011 années.
Finalement on obtient un peu plus de 5x109 siècles.
Nous retrouvons bien les 5 milliards de siècles de la légende.
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.
d'anneaux
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 28-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
Aucun commentaire:
Enregistrer un commentaire