Pourquoi pose-t-on $vₙ=hₙ+1$ ?

Pour éliminer la constante : le point fixe de $x↦2x+1$ est $-1$, et $hₙ-(-1)$ est géométrique. C'est la méthode générale pour $uₙ₊₁=auₙ+b$.

Question de mathsMathsSuites et récurrence

Combien de déplacements faut-il pour résoudre les tours de Hanoï ?

Q: Combien de fois le plus petit disque bouge-t-il ?

Une fois sur deux : $2ⁿ⁻¹$ fois. Les déplacements du plus petit disque alternent avec les autres.

Q: Combien de temps pour 20 disques à un coup par seconde ?

$2²⁰-1=1 048 575$ secondes, environ 12 jours.

Pour déplacer n disques, il faut déplacer n − 1 disques, puis le plus grand, puis à nouveau n − 1 disques : hₙ₊₁ = 2hₙ + 1, d'où hₙ = 2ⁿ − 1. Avec 64 disques, à un déplacement par seconde, il faudrait 585 milliards d'années.

Grand oral session 2027 : exposé de 10 minutes debout, puis 10 minutes d'échange, sans calculatrice. Plan prévu pour 10 min.

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

Enfant, j'ai joué aux tours de Hanoï sans savoir que la légende parle de moines déplaçant 64 disques d'or, et que la fin de leur travail marquerait la fin du monde. En terminale, j'ai pu calculer le nombre minimal de déplacements grâce aux suites et à la récurrence, et vérifier si la légende était inquiétante.

L'enjeu et les notions du programme

Modéliser un algorithme récursif par une suite arithmético-géométrique, trouver sa formule explicite et démontrer qu'elle est optimale.

Mathématiques

Suites définies par récurrence, suites arithmético-géométriques (première et terminale)
Raisonnement par récurrence (terminale)
Suites géométriques et somme de termes (première)
Algorithmique : fonction récursive (terminale)

Le plan de l'exposé en 10 min

1. Introduction : le jeu
1,5 min
Trois piquets, $n$ n disques de tailles différentes empilés sur le premier. On déplace un disque à la fois, sans jamais poser un disque sur un plus petit. Problématique : quel est le nombre minimal $h_{n}$ hₙ de déplacements pour transférer la tour sur le troisième piquet ?
2. Une stratégie récursive
3,5 min
Pour déplacer $n + 1$ n+1 disques : on déplace les $n$ n disques du haut sur le piquet intermédiaire ( $h_{n}$ hₙ coups), puis le grand disque sur le piquet d'arrivée (1 coup), puis les $n$ n disques sur le grand ( $h_{n}$ hₙ coups). Donc $h_{n + 1} = 2 h_{n} + 1$ hₙ₊₁=2hₙ+1, avec $h_{1} = 1$ h₁=1.
Cette stratégie est optimale : le grand disque ne peut bouger que si les $n$ n autres sont regroupés sur un même piquet, ce qui impose au moins $h_{n}$ hₙ coups avant et $h_{n}$ hₙ coups après. Les premières valeurs : 1, 3, 7, 15, 31.
3. Formule explicite
3,5 min
On conjecture $h_{n} = 2^{n} - 1$ hₙ=2ⁿ-1. Démonstration par récurrence : $h_{1} = 1 = 2^{1} - 1$ h₁=1=2¹-1 ; si $h_{n} = 2^{n} - 1$ hₙ=2ⁿ-1, alors $h_{n + 1} = 2 (2^{n} - 1) + 1 = 2^{n + 1} - 1$ hₙ₊₁=2(2ⁿ-1)+1=2ⁿ⁺¹-1.
Autre méthode : la suite $v_{n} = h_{n} + 1$ vₙ=hₙ+1 vérifie $v_{n + 1} = 2 v_{n}$ vₙ₊₁=2vₙ, elle est géométrique de raison 2 et $v_{1} = 2$ v₁=2, donc $v_{n} = 2^{n}$ vₙ=2ⁿ. C'est la technique générale pour les suites arithmético-géométriques.
Pour 64 disques : $2^{64} - 1 \approx 1, 8 \times 1 0^{19}$ 2⁶⁴-1≈1,8×10¹⁹ déplacements. À raison d'un par seconde, environ $5, 8 \times 1 0^{11}$ 5,8×10¹¹ années, quarante fois l'âge de l'Univers.
4. Conclusion
1,5 min
Il faut $2^{n} - 1$ 2ⁿ-1 déplacements, nombre que l'on obtient en traduisant la stratégie récursive par une suite, puis en la résolvant. La légende peut rassurer : les moines en ont pour des centaines de milliards d'années. J'ouvre sur la programmation récursive, où une fonction s'appelle elle-même exactement comme dans cette stratégie.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

h_{n + 1} = 2 h_{n} + 1, h_{1} = 1 \Rightarrow 1, 3, 7, 15, 31, \dots hₙ₊₁=2hₙ+1, h₁=1 \Rightarrow 1, 3, 7, 15, 31,\dots v_{n} = h_{n} + 1 : v_{n + 1} = 2 v_{n} \Rightarrow v_{n} = 2^{n} \Rightarrow h_{n} = 2^{n} - 1 vₙ=hₙ+1 : vₙ₊₁=2vₙ \Rightarrow vₙ=2ⁿ \Rightarrow hₙ=2ⁿ-1 h_{64} = 2^{64} - 1 \approx 1, 8 \times 1 0^{19} s \approx 5, 8 \times 1 0^{11} ans h₆₄=2⁶⁴-1\approx1,8\times10¹⁹ s \approx5,8\times10¹¹ ans

Conclusion : la réponse à la question

Le nombre minimal de déplacements est $2^{n} - 1$ 2ⁿ-1 : la stratégie récursive donne la relation $h_{n + 1} = 2 h_{n} + 1$ hₙ₊₁=2hₙ+1, dont on trouve la formule par récurrence ou par une suite auxiliaire géométrique. La croissance exponentielle rend le jeu impraticable dès quelques dizaines de disques.

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Pourquoi pose-t-on

v_{n} = h_{n} + 1

vₙ=hₙ+1 ?

Pour éliminer la constante : le point fixe de $x \mapsto 2 x + 1$ x↦2x+1 est $- 1$ -1, et $h_{n} - (- 1)$ hₙ-(-1) est géométrique. C'est la méthode générale pour $u_{n + 1} = a u_{n} + b$ uₙ₊₁=auₙ+b.

Écrivez la fonction récursive en Python.

def hanoi(n, depart, arrivee, inter) : si n > 0 : hanoi(n−1, depart, inter, arrivee) ; afficher le déplacement de depart vers arrivee ; hanoi(n−1, inter, arrivee, depart).

Combien de fois le plus petit disque bouge-t-il ?

Une fois sur deux : $2^{n - 1}$ 2ⁿ⁻¹ fois. Les déplacements du plus petit disque alternent avec les autres.

Combien de temps pour 20 disques à un coup par seconde ?

$2^{20} - 1 = 1048575$ 2²⁰-1=1 048 575 secondes, environ 12 jours.

Pourquoi la stratégie est-elle optimale ?

Parce que pour déplacer le plus grand disque, il faut que les n autres soient tous sur le troisième piquet, ce qui demande au moins hₙ coups, puis encore au moins hₙ pour les reposer dessus.

Les pièges qui coûtent des points

Donner la formule sans la démontrer.
Oublier de justifier l'optimalité de la stratégie.
Confondre 2ⁿ et 2ⁿ − 1.

Revoir les notions

Autres questions : suites et récurrence

Toutes les questions de maths →

Préparer l'oral, pas seulement le contenu

Gestion des 20 minutes de préparation, usage du tableau, posture debout, réponses au jury : la méthode complète, conforme aux règles de la session 2027.

Méthode : traiter une question de Grand oral →

Continuer la préparation

Le Grand oral 2027 →Méthode : traiter une question →Toutes les questions, par combinaison →Questions maths-physique-chimie →Questions maths-SES →Questions maths-SVT →Questions maths-NSI →Questions maths-SI →Questions maths-HGGSP →Questions maths-anglais →