De combien de façons peut-on monter un escalier en faisant des pas d'une ou deux marches ?

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.

Chaque matin, je monte les escaliers du lycée en sautant parfois une marche. Un jour, je me suis demandé combien de manières différentes j'avais de monter les 12 marches. En essayant de les compter, je me suis perdu. En NSI, on nous a appris à « penser récursivement » en regardant le dernier pas, et la réponse est apparue d'elle-même.

L'enjeu et les notions du programme

Construire une relation de récurrence par un raisonnement de dénombrement et la programmer efficacement.

Le plan de l'exposé en 9,5 min

1. 1. Introduction

   1 min

   On monte un escalier de $n$n marches en faisant des pas d'une ou de deux marches. Problématique : combien de suites de pas différentes permettent d'arriver en haut ?

2. 2. Mathématiques : penser au dernier pas

   4 min

   Notons $E(n)$E(n) le nombre de façons. Petits cas : $E(1)=1$E(1)=1 (un pas), $E(2)=2$E(2)=2 (1+1 ou 2), $E(3)=3$E(3)=3 (1+1+1, 1+2, 2+1).

   Pour $n\ge 3$n≥3, le dernier pas fait 1 ou 2 marches. S'il fait 1 marche, on était sur la marche $n-1$n-1, atteinte de $E(n-1)$E(n-1) façons. S'il en fait 2, on était sur la marche $n-2$n-2 : $E(n-2)$E(n-2) façons. Ces deux cas sont disjoints et couvrent tout, donc par le principe additif : $E(n)=E(n-1)+E(n-2)$E(n)=E(n-1)+E(n-2).

   On reconnaît la relation de Fibonacci : $E(n)=F_{n+1}$E(n)=Fₙ₊₁. Valeurs : 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 pour $n=1$n=1 à 10. Pour 12 marches, 233 façons ; pour 20 marches, $10946$10 946.

   Vérification par une autre méthode : avec $k$k pas de 2, il y a $n-2k$n-2k pas de 1, soit $n-k$n-k pas au total, dont on choisit les $k$k doubles : $\left(\genfrac{}{}{0ex}{}{n-k}{k}\right)$C(n-k, k). Pour $n=10$n=10 : $1+9+28+35+15+1=89$1+9+28+35+15+1=89.

3. 3. NSI : programmer la récurrence

   3 min

   La version récursive directe recalcule sans cesse les mêmes valeurs : son coût croît exponentiellement. En programmation dynamique, on remplit une liste E de proche en proche ou l'on garde seulement les deux dernières valeurs : $n$n additions.

   Le raisonnement se généralise : avec des pas de 1, 2 ou 3 marches, $E(n)=E(n-1)+E(n-2)+E(n-3)$E(n)=E(n-1)+E(n-2)+E(n-3). Le même schéma compte les façons de paver un couloir avec des dalles de longueur 1 et 2, ou les mots binaires sans deux 1 consécutifs.

4. 4. Conclusion

   1,5 min

   En regardant le dernier pas, on obtient la relation de Fibonacci : 89 façons pour 10 marches. Penser récursivement, c'est réduire un problème à des versions plus petites de lui-même. J'ouvre sur la croissance de ces nombres, proche de $1,618^n$1,618ⁿ.

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.

Conclusion : la réponse à la question

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.

Les pièges qui coûtent des points

• Oublier un des deux cas du dernier pas.
• Se tromper d'initialisation (E(2) = 2, pas 1).
• Confondre le nombre de pas et le nombre de marches.

Revoir les notions

• Combinatoire et dénombrement (Terminale spé maths) →
• Suites : récurrence et limites (Terminale spé maths) →

Autres questions : récursivité et récurrence

• Comment être sûr qu'un programme récursif donne toujours le bon résultat ?
• Pourquoi un programme récursif de quatre lignes met-il des secondes à calculer le 30ᵉ terme de Fibonacci ?
• Pourquoi un programme récursif peut-il « déborder » alors que le même calcul en boucle fonctionne ?
• Comment une figure dessinée par un programme récursif peut-elle avoir une aire nulle et une infinité de triangles ?

Toutes les questions maths-nsi →