Là Tour de Hanoï est un puzzle créé par le mathématicien français Édouard Lucas d’Amiens et présenté pour la première fois en 1883. Le jeu consiste à trois enjeux et d’une série de disques de différentes tailles qu’ils doivent être se déplacer en respectant des règles précises.
Lorsque le puzzle est sorti, il était accompagné d’une histoire conçue pour le rendre plus fascinant. D’après ceci légendele jeu serait la version simplifiée de la « Tour Sacrée de Brahma », une tour composée de 64 disques d’or qui doit être déplacé selon les mêmes règles que le puzzle et sur lequel les brahmanes du temple travaillent jour et nuit, en déplaçant un disque par seconde. La légende, dont il existe de nombreuses versions différentes, raconte que quand le dernier disque aura été déplacé, l’univers arrivera à sa fin.
Bien sûr, c’en est un histoire inventée pour accompagner le jeu, sans aucun fondement dans la vérité, mais cette idée soulève une question intéressante : combien de temps faudrait-il réellement pour résoudre un problème ? tour avec 64 disques si c’était possible un mouvement par seconde?
Voyons comment jouer à la Tour de Hanoï, comment la résoudre et combien de mouvements sont nécessaires pour résoudre la tour « Tour Sacrée de Brahma » et atteindre la fin de l’univers.
Comment jouer à la Tour de Hanoï
La tour de Hanoï se compose de trois enjeux et de certains disques (généralement 8) de différentes tailles, percés au centre pour pouvoir être insérés sur les poteaux. Au début du jeu, tous les disques sont sur le premier poteau, empilés du plus grand en bas au plus petit en haut.
Le but Et déplacer toute la tour vers le dernier messageen respectant quelques règles fondamentales :
- il peut être déplacé un seul disque à la fois;
- chaque mouvement consiste à déplacer un disque d’une tige à une autre. Il n’est pas possible, par exemple, de retirer un disque et de le placer temporairement hors des enchères ;
- Pas pouvez-vous jamais placer un disque plus grand sur un plus petit. Les disques doivent donc toujours rester ordonnés du plus grand en bas au plus petit en haut.
Comment résoudre la Tour de Hanoï et combien de mouvements cela prend
Pour comprendre comment se résout la Tour de Hanoï et combien de déplacements sont nécessaires, commençons par le cas le plus simple possible : une tour constituée d’un seul disque.
Un seul disque
Si nous avons un seul disquela solution est immédiate. Déplacez simplement le disque de la première à la dernière tige et le puzzle est résolu. C’est utile juste un geste.
Deux disques
Avec deux disques, la situation est encore simple, mais il faut commencer à réfléchir un peu. Si nous déplacions immédiatement le petit disque vers le dernier poteau, alors nous ne pourrions pas mettre le disque vert dessus (car il est plus gros) et nous perdrions des mouvements.
La séquence correcte est donc :
- on déplace le plus petit disque sur la tige centrale ;
- on déplace le plus gros disque vers la tige finale ;
- nous déplaçons enfin le plus petit disque sur la tige finale.
Nous recréons ainsi la tour sur la dernière tige en respectant toutes les règles. Pour deux disquesils sont donc utiles trois mouvements.
Trois disques
Avec trois disques la tour de Hanoï commence à nécessiter un véritable stratégie. Pour pouvoir recréer la tour dans le dernier post à droite, il faut s’assurer que le plus grand disque, qui se situe à la base de la tour, soit libre de se déplacer sur la tige de droite. Pour ce faire, nous devons déplacer temporairement les deux petits disques sur le pôle central.
On peut procéder ainsi :
- nous déplaçons le plus petit disque vers la tige droite ;
- on déplace le disque intermédiaire sur la tige centrale ;
- nous déplaçons le plus petit disque au-dessus du disque intermédiaire.
Comme auparavant, pour déplacer deux disques sur n’importe quel poteau, nous avons utilisé 3 mouvements. À ce stade, les deux petits disques sont sur la tige centrale et le plus grand disque est libre de se déplacer vers la tige droite, en utilisant un autre mouvement. Maintenant, avec 3 mouvements supplémentaires, nous transférons également les deux autres disques sur la dernière tige, recréant ainsi la tour.
Le nombre de coups est donc :
- 3 mouvements pour déplacer les deux petits disques sur le poteau central,
- 1 coup pour déplacer le plus gros disque sur la tige de droite,
- autre 3 mouvements pour déplacer à nouveau les deux petits disques et terminer la tour.
Au total, ils sont nécessaires 7 mouvements pour déplacer 3 disques.
La solution générale
Si nous essayons maintenant de penser à une tour avec 4 disquesle mécanisme devient plus clair :
- pour déplacer le plus grand disque, nous devons d’abord déplacer les trois petits disques sur la tige centrale. Comme nous l’avons vu, il faut 7 coups pour déplacer 3 disques.
- À ce stade, nous pouvons déplacer le plus grand disque sur la tige finale d’un seul mouvement.
- Finalement, nous devons à nouveau déplacer les trois disques sur le poteau final, ce qui nécessite 7 mouvements supplémentaires.
En tout:
7 + 1 + 7 = 15 coups
Et si on voulait déménager 5 disques? Nous utiliserions d’abord 15 mouvements pour déplacer 4 rondelles vers le poteau central, puis nous utiliserions un mouvement pour déplacer la plus grande rondelle vers le poteau droit, puis 15 autres mouvements pour répondre aux rondelles plus petites vers le poteau final.
Nous devrions donc utiliser 15 +1 +15 = 31 coups.
Et pour 6 disques ? Pour 8 ? Pour 64 ? Le raisonnement est toujours le même : pour déplacer une tour de X disques nous devons
- déplace les premiers X−1 disques sur une enchère intermédiaire
- déplacer le plus gros disque
- déplace-les à nouveau X−1 disques au-dessus de lui
Ce type de solution, dans laquelle pour comprendre quoi faire il faut regarder la solution du cas précédent, s’appelle solutions récursives et, précisément parce que la Tour de Hanoï dispose d’une solution de ce type, elle est souvent utilisée comme exemple lors des cours d’informatique pour apprendre à écrire des algorithmes récursifs.
Dans combien de secondes l’univers finira-t-il
Une autre façon, légèrement plus compacte, de décrire le nombre de mouvements nécessaires pour résoudre la Tour de Hanoï est la formule :
nombre de coups = 2(nombre de disques) – 1
En fait, avec deux disques, il nous en faut 22 – 1 = 4 – 1 = 3 coups, avec 3 disques il en faut 23 – 1= 8 – 1 = 7, avec 4 il en faut 24 – 1 = 15 et ainsi de suite.
Cette formule est très utile pour calculer le nombre de coups nécessaires pour résoudre la Tour de Brahma, composée de 64 disques d’or, sans avoir à calculer toutes les étapes précédentes. En appliquant la formule que nous avons, il en faut 264 − 1 coup. Si l’on imagine que les moines parviennent à faire un mouvement par seconde, l’univers se terminera 18 446 744 073 709 551 615 secondes après le début du jeu, soit environ 585 milliards d’années. Bref, rien d’inquiétant.