Monter les escaliers

Date 1 février 2016 Catégories "Maths" par VulgaireDev

L'énoncé est très simple : vous êtes face à un escalier de n marches, et vous ne pouvez les monter que de deux façons, soit en grimpant d'une seule marche, soit en grimpant de deux. Combien il y a-t-il de façons différentes de gravir cet escalier ?

Commençons par essayer pour quelques valeurs de n.

Un escalier numéroté (pour visualiser)

 

Pour n=1, on a une 1 possibilité : sauter une marche, qu'on notera 1

Pour n=2, on a 2 possibilités : 1-1 ou 2

Pour n=3, on a 3 possibilités : 1-1-1, 1-2, et 2-1

Pour n=4, on a 5 possibilités : 1-1-1-1, 1-1-2, 1-2-1, 2-1-1, 2-2

Pour n=5, on a 8 possibilités (je ne vais pas détailler mais croyez moi)

Si on regarde les résultats, on peut conjecturer qu'on a affaire à la suite de Fibonacci, qui est définie de la manière suivante :

\(U_0,U_1 = 1 \)

\(U_{n} = U_{n-1}+ U_{n-2}\)

Pour n=3, on a bien 2+1 = 3 possibilités, pour n=4 on a 3+2=5, pour n=5 on en a 4+3=8 etc.

Est ce que cette conjecture correspond bien à la réalité ?

En fait, les solutions au rang n sont composées des solutions du rang n-1 auxquelles on concatène un saut de 1 marche, et des solutions du rang n-2 auxquelles on concatène un saut de 2 marches. C'est tout.

Pourquoi?

Au rang n-1, il y a n-1 marches, donc en rajouter une résout bien le problème au rang n. Idem pour le rang n-2, rajouter 2 résout bien le problème au rang n.

Notons Sol(n-i)|i la concaténation de i aux solutions du rang n-i. Ici on a donc : 

\(Sol(n-2)|2\subseteq Sol(n)\)

\(Sol(n-1)|1\subseteq Sol(n)\)

Pourquoi ne continue-t-on pas avec n-3 etc ? Tout simplement parce que si tel était le cas, on devrait rajouter un 3 (dans le cas du rang n-3) pour que la solution fonctionne au rang n, or on ne peut pas monter 3 marches d'un coup, on ne peut qu'exprimer 3 en décomposition de 1 et de 2, ce qui correspond déjà à des solutions comprises dans les rang n-1 et n-2 !

NB : N'aurait-on pas des solutions qui se recoupent entre celles de n-2 et celles de n-1? Non, car dans un cas elle finiront par un 1, et dans l'autre par un 2, ces deux ensembles sont donc disjoints.

On a alors :

\((Sol(n-2)|2 \cup Sol(n-1)|1)\subseteq Sol(n)\)

Donc là on a prouvé que les solutions du rang n-1 auxquelles on ajoute 1 et celles du rang n-2 auxquelles on ajoute 2 sont incluses dans celles du rang n.

Il faut maintenant prouver la réciproque afin de montrer que ce sont les seules solutions, et qu'il n'y en a pas d'autres.

C'est trivial: retrancher le dernier membre (1 ou 2) de toute solution au rang n nous donne forcément une solution du rang n-1 ou n-2 !

On a donc :

\(Sol(n)\subseteq (Sol(n-2)|2 \cup Sol(n-1)|1)\)

Donc:

\(Sol(n) \Leftrightarrow (Sol(n-2)|2 \cup Sol(n-1)|1)\)

On a bien prouvé la réciproque, et donc que le nombre de solutions au rang n correspond au nième terme de la suite de Fibonacci.

Commentaires

blog comments powered by Disqus