Tours de Hanoï
Les tours de Hanoï sont un casse-tête mathématique classique. Trois tiges, une pile de disques de tailles différentes et deux règles strictes : déplacer un disque à la fois, et ne jamais poser un disque plus grand sur un plus petit.
Trois tiges et un cône de disques
Le plateau comporte trois tiges. Les disques sont tous de tailles différentes et s’enfilent sur les tiges. Au départ, tout le jeu se trouve sur une tige, rangé par taille, le plus grand en bas et le plus petit en haut : la pile forme un cône. Le but est de déplacer toute cette tour sur une autre tige.
Les trois règles
1. Ne déplacez qu’un disque à la fois. 2. Un coup prend le disque du dessus d’une pile et le pose sur une autre pile, ou sur une tige vide. 3. Un disque plus grand ne doit jamais reposer sur un plus petit. Ces trois règles constituent tout le jeu. Avec elles, chaque position autorisée est une façon de répartir les disques sur les tiges en gardant chaque tige triée.
La solution la plus courte est 2ⁿ − 1
Le plus petit nombre de coups qui résout une tour de n disques est 2ⁿ − 1. Un disque demande 1 coup. Deux disques en demandent 3. Trois en demandent 7, quatre 15 et cinq 31. Chaque nouveau disque double la solution précédente et ajoute le coup qui déplace le plus grand disque : si n − 1 disques demandent T coups, n disques en demandent 2T + 1. Cette récurrence donne exactement 2ⁿ − 1. Huit disques, la plus grande tour de l’application PictorX, demandent 255 coups. Il n’existe aucun chemin autorisé plus court.
Comment fonctionne la récursion
Pour déplacer n disques de la tige de départ à la tige d’arrivée, en utilisant la tige restante comme tige auxiliaire : 1. Déplacez les n − 1 disques du haut de la tige de départ vers la tige auxiliaire. 2. Déplacez le plus grand disque de la tige de départ directement sur la tige d’arrivée. 3. Déplacez les n − 1 disques de la tige auxiliaire sur la tige d’arrivée, par-dessus le plus grand disque. L’étape 2 est autorisée parce que le plus grand disque peut aller sur n’importe quelle tige. Les étapes 1 et 3 sont le même casse-tête, avec un disque de moins. L’appel s’arrête à un seul disque, qui se déplace une fois. En le déroulant, on obtient les 2ⁿ − 1 coups, et aucune étape ne pose jamais un disque plus grand sur un plus petit.
La légende des 64 disques d’or
Le mathématicien français Édouard Lucas a présenté ce casse-tête en 1883. Il l’accompagnait d’une légende sur un temple indien de Kashi Vishwanath, où des prêtres déplacent une pile de 64 disques d’or selon ces mêmes règles. Quand le dernier coup sera joué, dit la légende, le monde prendra fin. Soixante-quatre disques demandent 2⁶⁴ − 1 coups : 18 446 744 073 709 551 615. À raison d’un coup parfait par seconde, jour et nuit, cela fait environ 585 milliards d’années. Les prêtres n’ont pas fini.
Jouez dans PictorX
Ouvrez Tours de Hanoï : une tour de quatre disques est déjà sur la tige de départ. Quinze coups, c’est le minimum. Faites glisser le disque du dessus vers une autre tige, ou cliquez sur une tige puis sur celle que vous voulez. Les touches 1, 2 et 3 font la même chose. Un disque plus grand sur un plus petit est refusé. Disques va de 1 à 8 : vous pouvez donc comparer 1, 3, 7, 15, 31, 63, 127 et 255 à la formule. Étape joue un coup d’une solution la plus courte. Résoudre joue le reste. « Regarder 3 disques » montre la stratégie récursive en mouvement. Annuler et Rétablir parcourent vos coups. Enregistrez un PNG, ou ouvrez le plateau dans l’éditeur PictorX.
Questions fréquemment posées
Quelles sont les règles des tours de Hanoï ?
Déplacez un disque à la fois. Prenez le disque du dessus d’une tige et posez-le sur une autre tige. Ne posez jamais un disque plus grand sur un plus petit. Toute la tour part d’une tige et doit finir sur une autre.
Combien de coups demande la solution la plus courte ?
2ⁿ − 1. Un disque, c’est 1 coup, deux disques 3, trois 7, quatre 15 et cinq 31. Chaque disque ajouté double la solution précédente et ajoute un coup.
Qui a inventé les tours de Hanoï ?
Le mathématicien français Édouard Lucas l’a présenté en 1883. L’histoire des prêtres et des 64 disques d’or de Kashi Vishwanath est la légende qu’il a associée au casse-tête.
Combien de temps prendraient 64 disques ?
2⁶⁴ − 1 coups, soit 18 446 744 073 709 551 615. À un coup par seconde, cela fait environ 585 milliards d’années.
Outils associés
Tours de Hanoï
Déplacez une tour de disques sur trois tiges dans votre navigateur. Un disque à la fois, jamais un grand sur un petit. La solution la plus courte compte 2ⁿ − 1 coups.
Aiguille de Buffon
Lâchez des aiguilles sur un plancher rayé, dans votre navigateur. Comptez les croisements et regardez l’expérience de Buffon de 1777 estimer π.
Aiguille de Buffon
Le problème de l’aiguille de Buffon (1777) : pourquoi une aiguille lâchée sur des lignes parallèles estime π, comment la probabilité 2l/(πd) de l’aiguille courte vient de l’aire sous une courbe sinus, et pourquoi l’expérience converge lentement.
Cercles de multiplication
Reliez chaque nombre d’un cercle à son multiple. Dessinez une table de multiplication, une cardioïde ou une figure en fil sur papier, à la craie ou sur bois.
La conjecture de Collatz
Explorez le problème de Collatz 3n+1 dans votre navigateur. Parcourez les suites de grêlons, faites pousser un arbre de Collatz géométrique et zoomez dans la fractale de Collatz continue.
Fourmi de Langton
Lancez la fourmi de Langton dans votre navigateur. Observez la symétrie, le chaos et l’autoroute de 104 pas, puis essayez des règles multicolores, plusieurs fourmis, une grille hexagonale et des turmites.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Jouer aux tours de Hanoï