La tour de Hanoï est un puzzle idéal pour un projet de vacances d’élève de primaire. En ajoutant les disques un à un et en cherchant « le plus petit nombre de coups », on découvre une étonnante règle des nombres. Le matériel se fabrique soi-même, et l’on peut tout présenter en un jour ou quelques jours. (Au Japon, les écoliers ont un devoir de vacances libre appelé « jiyū kenkyū », un petit projet de recherche personnel. C’est de cela qu’il s’agit ici.)
Exemples de sujets de recherche
- Quand on ajoute un disque, comment change le nombre minimal de coups ?
- S’il y avait 64 disques, combien d’années faudrait-il pour tout déplacer ?
- Combien de fois le plus petit disque bouge-t-il ?
Ici, je présente la démarche pour le premier sujet.
Ce qu’il faut préparer
- Une tour de Hanoï (on peut la fabriquer avec du carton ou des pièces de monnaie, comme dans l’article sur la fabrication ; 6 disques, c’est confortable)
- Un cahier pour noter, et un crayon
- Si possible, une feuille de pointage pour compter les coups (par traits groupés par cinq), ou un compteur
On peut aussi essayer sur le plateau en bas de cette page.
Déroulement de l’expérience
- Vérifier les règles : on ne déplace qu’un disque à la fois ; on ne pose jamais un grand disque sur un petit ; on a gagné quand toute la tour de gauche est passée à droite.
- Commencer avec 1 disque : on résout avec 1 disque, puis 2, puis 3… en ajoutant un disque à chaque fois.
- Compter les coups : chaque déplacement compte pour 1 coup.
- Recommencer plusieurs fois et noter le plus petit nombre de coups : au début, on peut faire des détours. En recommençant, on trouve le nombre qu’on ne peut plus réduire.
Exemple de tableau
| Nombre de disques | Nombre minimal de coups | Lien avec le nombre précédent |
|---|---|---|
| 1 disque | 1 coup | ― |
| 2 disques | 3 coups | 1 × 2 + 1 |
| 3 disques | 7 coups | 3 × 2 + 1 |
| 4 disques | 15 coups | 7 × 2 + 1 |
| 5 disques | 31 coups | 15 × 2 + 1 |
| 6 disques | ? | ? |
Les nombres du tableau sont les réponses quand tout est bien fait. Comptez d’abord vous-même, puis comparez après.
Trouver la règle
Quand vous avez toutes vos notes, regardez bien la suite des nombres de coups : « 1, 3, 7, 15, 31 ».
- En multipliant le nombre précédent par 2 et en ajoutant 1, on obtient le suivant : 3 × 2 + 1 = 7, 7 × 2 + 1 = 15.
- En ajoutant 1 aux nombres de coups, on obtient 2, 4, 8, 16, 32, des nombres qui doublent à chaque fois.
Cherchez aussi pourquoi c’est « multiplier par 2 et ajouter 1 ». Pour déplacer 4 disques, par exemple, il faut :
- Écarter les 3 disques du haut sur la tige centrale (autant de coups que pour déplacer 3 disques)
- Déplacer le plus grand disque à droite (1 coup)
- Déplacer les 3 disques du milieu à droite (de nouveau autant de coups que pour 3 disques)
Cela fait deux fois le nombre de coups de 3 disques, plus 1 coup. C’est pour cela que c’est « multiplier par 2 et ajouter 1 ».
Prédire, puis vérifier
Quand vous avez la règle, prédisez le nombre de coups pour 6 disques, puis vérifiez en le faisant vraiment. Ce devrait être 31 × 2 + 1 = 63 coups. Si la prédiction se réalise, cela confirme que la règle est juste.
Poursuivez ensuite avec 7 disques (127 coups) et 10 disques (1 023 coups). Avec 64 disques, le nombre devient énorme : même à un coup par seconde, il faut environ 584,5 milliards d’années (Combien d’années faut-il pour déplacer 64 disques ?).
Exemple de présentation
Pour une affiche sur grand papier ou sur carton, l’ordre suivant est facile à suivre.
- Ce qui a donné envie de chercher : comment vous avez connu la tour de Hanoï, ce qui vous a surpris.
- Les règles de la tour de Hanoï : les expliquer avec un dessin.
- La méthode : jusqu’à combien de disques, et comment vous avez compté.
- Les résultats : le tableau et le graphique du nombre de coups (avec le nombre de disques en abscisse et le nombre de coups en ordonnée, on voit la courbe monter en flèche).
- Ce que vous avez découvert : la règle trouvée, et pourquoi.
- Votre avis, et ce que vous voudriez chercher encore : la légende des 64 disques, ce qui se passe avec quatre tiges, etc.
Si vous présentez aussi l’histoire et la légende de la tour de Hanoï (Origine et légende), votre exposé sera plus agréable à lire.
À vous de jouer
Le plateau ci-dessous commence avec 3 disques. Changez le nombre de disques et cherchez le plus petit nombre de coups. Il compte aussi les coups pour vous.
