Tours de Hanoï

La légende raconte qu'un temple à Bénarès, en Inde, possède trois piquets où des moines déplacent 64 disques dorés d'un piquet à un autre, jour et nuit. Le jour où ils terminent, le monde prend fin. Effrayant ? Une fois que vous verrez comment le nombre de mouvements augmente, vous saurez à quel point ce « jour du jugement » est réellement éloigné.

Seulement trois règles

L'objectif : transporter toute une pile de disques du piquet de gauche au piquet de droite.

Déplacer un disque à la fois, et seulement le disque le plus haut d'un piquet ;
Un disque ne peut reposer que sur un piquet ;
Un disque plus grand ne doit jamais reposer sur un plus petit.

Les règles sont simples, mais la troisième est une mine : poser un grand disque sur un petit ruine la tentative sur-le-champ. Au fait, le plus petit disque est le plus libre — il peut reposer sur n'importe quoi et ne viole jamais une règle.

Résoudre avec trois disques

Penser à trois disques en même temps devient compliqué. L'astuce : maîtriser deux disques, et trois disques suivront.

Pour déplacer 3 disques sur le piquet cible :

D'abord, déplacer les 2 disques du haut sur le piquet du milieu de rechange (3 mouvements) ;
Déplacer le plus grand disque directement sur le piquet cible (1 mouvement) ;
Déplacer les 2 disques du piquet de rechange par-dessus (3 mouvements).

$3 + 1 + 3 = 7$ mouvements, c'est fait. Remarquez-vous quelque chose ? « Déplacer 2 disques » s'est produit deux fois — la grande tâche a été divisée en deux plus petites tâches plus un mouvement supplémentaire.

Quatre disques fonctionnent de la même manière : déplacer 3 disques vers le piquet de rechange (7 mouvements), déplacer le plus grand disque (1 mouvement), remettre les 3 disques par-dessus (7 mouvements) — 15 au total. Si vous pouvez déplacer n−1 disques, vous pouvez déplacer n. Cette route n'a pas de fin et fonctionne toujours.

InteractifTours de Hanoï

Comment utiliser

Disques

Coups: 0Minimum: 7

Déplace un disque à la fois ; ne place jamais un disque plus grand sur un plus petit

Le nombre de mouvements : 1, 3, 7, 15, 31…

Comptez les mouvements minimums :

Disques	1	2	3	4	5
Mouvements minimums	1	3	7	15	31

Le motif est double, puis ajoutez 1 : $3 = 1 \times 2 + 1$ , $7 = 3 \times 2 + 1$ , $15 = 7 \times 2 + 1$ … écrit comme une formule :

$2^n - 1$

Pour n disques, le minimum est de $2^n - 1$ mouvements. Cela correspond exactement à la stratégie : déplacer n disques = déplacer n−1 disques deux fois + déplacer le grand disque une fois.

Pourquoi 64 disques ne se terminent jamais

Faites le calcul

$2^{64} - 1 \approx 1.8 \times 10^{19}$ . Même à un disque par seconde, sans s'arrêter, les moines auraient besoin d'environ 585 milliards d'années — plus de 40 fois l'âge de l'univers (environ 14 milliards d'années). Le monde est en sécurité.

C'est le côté effrayant de la croissance exponentielle : ajouter un disque est une petite étape, mais le nombre de mouvements double presque. Passer de 5 disques à 10 augmente le minimum de 31 à 1023 — encore seulement environ 17 minutes à un mouvement par seconde, pas de problème du tout ; à 20 disques, il dépasse un million de mouvements. Tout ce qui double à chaque étape devient très vite inimaginable.

Vérifiez vos connaissances

Quiz rapide

0 / 3 correct0 / 3 correct

1. Quel est le nombre minimum de mouvements pour 3 disques ?
2. En passant de 3 disques à 4, le minimum passe de 7 à combien ?
3. Pourquoi la légende des 64 disques ne sera-t-elle jamais terminée ?