Déplacer 3 disques, tu peux y arriver en quelques essais. Mais à 5 ou 7 disques, ça prend soudain beaucoup plus de temps, et à 10 disques, le nombre de déplacements nécessaires est presque trop grand pour être compté à la main. Pourquoi un seul disque de plus rend-il les choses si brusquement plus difficiles ? La réponse : les tours de Hanoï sont un problème qui grandit de façon « exponentielle ».
Les règles sont simples. Il y a trois tiges, et les disques empilés par ordre de taille sur la première tige doivent tous être déplacés sur la troisième. Il y a exactement deux conditions : on ne déplace qu'un disque à la fois, et on ne pose jamais un grand disque sur un plus petit. Pour n disques, le nombre minimal de déplacements est exactement 2ⁿ − 1. Cela fait 1 déplacement pour 1 disque, 3 pour 2 disques, 7 pour 3 disques, 15 pour 4 disques… le nombre de déplacements nécessaires double presque à chaque disque ajouté.
Pourquoi exactement 2ⁿ−1 ? Pour déplacer n disques, on déplace d'abord les n−1 disques du haut (tous sauf le grand du bas) sur la tige intermédiaire — ce qui demande déjà à lui seul 2ⁿ⁻¹−1 déplacements —, puis on déplace le disque du bas sur la tige d'arrivée (1 déplacement), et enfin on ramène les n−1 disques de la tige intermédiaire sur la tige d'arrivée (encore 2ⁿ⁻¹−1 déplacements). En équation, cela donne (2ⁿ⁻¹−1) + 1 + (2ⁿ⁻¹−1) = 2ⁿ−1. Cette méthode — « ramener un grand problème à un problème plus petit exactement de la même forme » — s'appelle la récursivité. Les tours de Hanoï sont l'exemple le plus célèbre pour apprendre à raisonner de façon récursive, et un classique quand les étudiants en informatique apprennent à programmer.
Une célèbre légende relie ce casse-tête à un temple indien. Des moines y déplaceraient 64 disques d'or selon cette même règle, et le monde prendrait fin quand ils auront terminé. Le nombre minimal de déplacements pour 64 disques est 2⁶⁴−1 — même en déplaçant un disque par seconde sans jamais s'arrêter, il faudrait environ 585 milliards d'années, bien plus que l'âge de l'Univers lui-même (environ 13.8 milliards d'années). Grâce à cette légende, les tours de Hanoï sont souvent citées comme l'exemple type de la vitesse effrayante à laquelle une quantité à croissance exponentielle peut exploser.
Ce genre de croissance exponentielle compte aussi bien au-delà des tours de Hanoï. Des bactéries dont le nombre double à intervalles réguliers, une feuille de papier qui devient incroyablement épaisse après seulement quelques pliages — tout cela repose sur le même principe. Peu d'exemples font sentir aussi bien que les tours de Hanoï qu'« une règle d'apparence modeste, répétée, peut grandir bien au-delà de ce qu'on imagine ».
Pour essayer avec des enfants, commencez par 3 disques et faites-leur résoudre le casse-tête en un minimum de déplacements (7), puis passez à 4 disques (15) et à 5 disques (31), en notant à chaque fois « combien de déplacements il a fallu ». Constater par eux-mêmes que le nombre de déplacements fait un peu plus que doubler à chaque disque ajouté rend la notion abstraite de croissance exponentielle bien plus concrète.
Sur notre page d'activité, tu peux choisir une difficulté de 3 à 6 disques et essayer toi-même, en comparant en temps réel ton nombre de déplacements au minimum théorique. Mets-toi au défi de le résoudre en exactement le nombre minimal de déplacements.