La tour de Hanoï revient souvent, dans les manuels et les examens d’entrée, comme sujet de relations de récurrence et de démonstration par récurrence (au Japon, dans le cours « mathématiques B » du lycée). Dans cet article, nous nous exerçons à raisonner en résolvant des exemples. Les disques sont numérotés 1, 2, 3… du plus petit au plus grand, et le nombre minimal de coups pour déplacer une tour de n disques est noté aₙ.
Exemple 1 : poser la relation de récurrence
Énoncé : Il y a trois tiges A, B et C, et n disques de tailles différentes sont empilés sur A, du plus grand au plus petit. On déplace un disque à la fois, sans jamais poser un grand disque sur un petit, pour amener tous les disques sur C. En notant aₙ le nombre minimal de coups, exprimer aₙ₊₁ en fonction de aₙ.
Solution : Regardons le plus grand disque (le numéro n+1). Pour le déplacer sur C, il faut qu’à cet instant les n disques du dessus soient tous empilés sur B.
- Déplacer les n disques du haut de A vers B … au minimum aₙ coups
- Déplacer le disque n+1 de A vers C … 1 coup
- Déplacer les n disques de B vers C … au minimum aₙ coups
Avec cette méthode, on déplace n+1 disques, donc aₙ₊₁ ≤ 2aₙ + 1. Inversement, quelle que soit la méthode, les coups des étapes 1 à 3 sont toujours nécessaires, donc aₙ₊₁ ≥ 2aₙ + 1. Donc,
aₙ₊₁ = 2aₙ + 1 (a₁ = 1)
Aux examens, on peut demander de montrer à la fois « ≤ » et « ≥ » pour affirmer l’égalité. Une explication détaillée se trouve dans la formule du nombre minimal de coups.
Exemple 2 : trouver le terme général
Énoncé : Trouver le terme général de la suite définie par a₁ = 1 et aₙ₊₁ = 2aₙ + 1.
Solution : Une relation de récurrence de la forme aₙ₊₁ = paₙ + q se transforme à l’aide du nombre α qui vérifie α = 2α + 1. Comme α = −1, on ajoute 1 aux deux côtés :
aₙ₊₁ + 1 = 2(aₙ + 1)
La suite aₙ + 1 est une suite géométrique de premier terme a₁ + 1 = 2 et de raison 2. Donc aₙ + 1 = 2 · 2ⁿ⁻¹ = 2ⁿ, et
aₙ = 2ⁿ − 1
Pour vérifier, assurons-nous que a₁ = 1, a₂ = 3 et a₃ = 7 sont compatibles avec la relation de récurrence.
Exemple 3 : démontrer par récurrence
Énoncé : Démontrer par récurrence que le nombre minimal de coups pour déplacer n disques est 2ⁿ − 1.
Solution :
- Pour n = 1, un disque se déplace en 1 coup et on ne peut pas faire moins, donc le nombre minimal de coups est 1 = 2¹ − 1 : la propriété est vraie.
- On suppose que, pour n = k, le nombre minimal de coups est 2ᵏ − 1. Pour n = k+1, d’après l’idée de l’exemple 1, le nombre minimal de coups est 2(2ᵏ − 1) + 1 = 2ᵏ⁺¹ − 1, donc la propriété est vraie aussi pour n = k+1.
- D’après 1 et 2, la propriété est vraie pour tout entier naturel n.
Le point clé est que le « à la fois ≤ et ≥ » de l’exemple 1 est utilisé à l’étape 2 de la récurrence.
Exemple 4 : quand on ne peut aller que sur la tige voisine
Énoncé : Les tiges A, B et C sont alignées, et les disques ne peuvent aller que entre A et B, et entre B et C (on ne peut pas aller directement de A à C). Trouver le nombre minimal de coups bₙ pour déplacer n disques de A à C.
Solution : Le plus grand disque, n, doit être déplacé deux fois : A → B → C.
- Déplacer les n−1 disques du haut de A vers C … bₙ₋₁ coups (pour mettre n sur B, il faut que B soit libre)
- Déplacer le disque n de A vers B … 1 coup
- Déplacer les n−1 disques de C vers A … bₙ₋₁ coups (pour mettre n sur C, il faut que C soit libre)
- Déplacer le disque n de B vers C … 1 coup
- Déplacer les n−1 disques de A vers C … bₙ₋₁ coups
Donc bₙ = 3bₙ₋₁ + 2 (b₁ = 2). De α = 3α + 2, on tire α = −1, donc bₙ + 1 = 3(bₙ₋₁ + 1). La suite bₙ + 1 est une suite géométrique de premier terme 3 et de raison 3, donc
bₙ = 3ⁿ − 1
Pour 1 à 6 disques, un calcul qui examine toutes les dispositions confirme aussi que ce nombre de coups est minimal. Fait amusant : pendant ces 3ⁿ − 1 coups, on passe une fois par chacune des 3ⁿ dispositions possibles (le nombre de dispositions est dans l’article sur les régularités).
Exemple 5 : exercices
Pour finir, essayez vous-même. Les réponses sont en dessous.
- Trouver le nombre minimal de coups pour 10 disques.
- À partir de combien de disques le nombre minimal de coups dépasse-t-il 1 000 ?
- Quand on déplace n disques en un nombre minimal de coups, combien de fois le plus petit disque bouge-t-il ?
Réponses : 1. 2¹⁰ − 1 = 1 023 coups. 2. De 2ⁿ − 1 > 1000, on tire 2ⁿ > 1001 ; comme 2⁹ = 512 et 2¹⁰ = 1024, c’est à partir de 10 disques. 3. 2ⁿ⁻¹ fois (la raison est dans « Combien de fois chaque disque bouge » de l’article sur les régularités).
