🎛️ Résous les Tours de Hanoï en regardant l'algorithme bosser
Choisis le nombre de disques (1 à 8) et appuie sur « Résoudre ». L'algorithme récursif fait son œuvre en − 1 mouvements optimaux.
Mouvements effectués
0
Optimal : − 1
15
Temps à 1 mvt/sec
15 sec
n = 4 disques : 15 mouvements optimaux. Appuie sur « Résoudre » pour voir l'algorithme.
🗼 Le problème (1883, Édouard Lucas)
François Édouard Anatole Lucas, mathématicien français, invente en 1883 un jeu qui deviendra l'exemple culte de la récursion. Le décor :
- Trois tours verticales (notées A, B, C).
- Sur la tour A, n disques empilés du plus grand (en bas) au plus petit (en haut).
- Objectif : déplacer tous les disques de A vers C.
- Règles :
- On ne bouge qu'un seul disque à la fois.
- On ne peut jamais poser un disque plus grand sur un disque plus petit.
- On utilise les trois tours comme intermédiaires.
Avec 1 disque, c'est trivial : 1 mouvement (A → C). Avec 2 disques, 3 mouvements. Avec 3 disques, 7 mouvements. Avec 4 disques, 15 mouvements. Une suite : 1, 3, 7, 15, 31, 63, …
Théorème (suite minimale)
Le nombre minimum de mouvements pour déplacer n disques est :
M(n) = − 1
💡 L'idée géniale : la récursion
Comment savoir résoudre Hanoï avec 100 disques ? Tu ne vas pas tout faire à la main. Tu vas utiliser la récursion. Voici l'algorithme :
Algorithme Hanoï(n, source, dest, aux) :
- Si n = 1 : déplace le disque de source → dest.
- Sinon :
- Hanoï(n − 1, source, aux, dest) // bouge n−1 disques sur la tour auxiliaire
- Déplace le grand disque source → dest // 1 mouvement
- Hanoï(n − 1, aux, dest, source) // bouge n−1 disques sur la destination
Cette élégance est presque magique. L'algorithme s'auto-appelle deux fois, et résout le problème en un nombre exponentiel de mouvements. C'est la définition même d'une récursion exponentielle.
📐 La démonstration de M(n) = − 1
Le coût total respecte la relation de récurrence :
M(n) = 2·M(n − 1) + 1, avec M(1) = 1
Démonstration par récurrence :
- Initialisation : M(1) = 1 = − 1. ✓
- Hérédité : suppose M(n − 1) = − 1. Alors :
M(n) = 2·( − 1) + 1 = − 2 + 1 = − 1. ✓
QED. C'est l'un des exercices de récurrence les plus élégants — et il revient régulièrement aux Olympiades.
🕉️ La légende du Bouddha de Bénarès
Lucas accompagne son jeu d'une légende somptueuse :
Combien de temps cela prend-il ? Calcule : − 1 = 18 446 744 073 709 551 615 mouvements. À 1 mouvement par seconde, ça ferait environ 585 milliards d'années. L'univers a 13.8 milliards d'années. Le moine bouddhiste a encore 99.998% du travail à faire.
⚡ La complexité exponentielle : un mur infranchissable
Avec 30 disques : 1 milliard de mouvements. Faisable en quelques secondes sur un ordinateur. Avec 60 disques : mouvements. Même 1 milliard d'opérations/seconde ne suffit pas — il faudrait 30 ans à un superordinateur. Avec 100 disques : impossible avant la fin de l'univers.
Hanoï est l'exemple parfait d'un problème qui a une solution simple (l'algorithme en 3 lignes) mais une complexité catastrophique. C'est exactement la frontière entre P et EXPTIME en informatique théorique. Au-delà d'une certaine taille, peu importe la puissance de calcul disponible : tu ne pourras pas résoudre.
🎯 Hanoï et le triangle de Pascal (lien magique)
Connecte deux numéros consécutifs d'une « solution optimale » de Hanoï à n disques, et tu obtiens une trajectoire dans un graphe en forme de Sierpinski (oui, le triangle fractal de la Catégorie B). L'algorithme de Hanoï est isomorphe à un parcours d'arbre dans un Sierpinski discret.
Cette connexion étonnante a été démontrée en 1981 par Andreas Hinz. C'est l'illustration parfaite de l'unité des mathématiques : récursion (Hanoï), fractale géométrique (Sierpinski), et combinatoire (parcours d'arbre) sont en réalité le même objet sous trois angles différents.
📐 Comment ça tombe au BAC SM
Hanoï n'est pas dans le programme officiel, mais c'est un terrain de jeu idéal pour pratiquer :
- Suites récurrentes : la relation M(n) = 2·M(n−1) + 1 est le cas type d'une suite arithmético-géométrique du 2BAC SM.
- Récurrence forte : la démonstration de la formule M(n) = − 1 est un exercice de récurrence parfait pour s'entraîner.
- Algorithmique récursive (bonus pour ceux qui programment) : Hanoï est l'exemple culte de récursion en informatique.
- Démonstration par récurrence d'une formule explicite : technique exigée à chaque session du bac SM.
🌍 Variantes et généralisations
- Hanoï à 4 tours (problème de Frame-Stewart, 1941) : avec 4 tours au lieu de 3, la solution optimale n'est pas connue dans le cas général. Un problème ouvert pendant 80 ans.
- Hanoï bicolore : alterner les disques de deux couleurs avec contraintes.
- Hanoï cyclique : on ne peut bouger les disques que dans un sens A → B → C → A.
- Hanoï à plusieurs disques par mouvement : on peut prendre la pile entière.
Vérifie ta compréhension
3 questions courtes pour valider tes acquis. Tu peux réessayer.