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.

  1. Déplacer les n disques du haut de A vers B … au minimum aₙ coups
  2. Déplacer le disque n+1 de A vers C … 1 coup
  3. 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 :

  1. 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.
  2. 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.
  3. 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.

  1. 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)
  2. Déplacer le disque n de A vers B … 1 coup
  3. Déplacer les n−1 disques de C vers A … bₙ₋₁ coups (pour mettre n sur C, il faut que C soit libre)
  4. Déplacer le disque n de B vers C … 1 coup
  5. 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.

  1. Trouver le nombre minimal de coups pour 10 disques.
  2. À partir de combien de disques le nombre minimal de coups dépasse-t-il 1 000 ?
  3. 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).