Bijour

Je suis de retour avec un exo que ma prof de maths veut qu'on trouve absolument Je vous le donne, mettez moi sur la voie !

Charlotte (Ah ok ) doit monter un escalier de "n" marches (n dans IN*). Elle est capable de monter les marches une à une ou deux à deux (Comme Franklin ). De combien de façons peut elle monter cet escalier ?

Merci de votre aide !

Non jeune homme je ne ferai pas ton travail

On dirait un exercice sur les arrangements.

C'est du dénombrement apparemment, mais on doit donner à la fin une expression en fonction de "n"...

On note E(x) la partie entière de x.

Si l'escalier comporte n marches, tu peux placer de 0 à E(n/2) groupement de 2 marches lors de la montée.
Pour un nombre k de groupements de 2 marches considéré, il y a C(k,n-k) façons de le placer sur les n marches.
La réponse est donc : somme pour k allant de 0 à E(n/2) de C(k,n-k).

J'ai pas bien compris ce que tu as fait

Prend des cas particuliers, ça t'aidera à comprendre.

Tu peux monter 4 marches de la façon suivante :
(1,1,1,1),(2,1,1),(1,2,1),(1,1,2),(2,2).

Il y a 3 cas à distinguer :
1- Le cas où on ne monte jamais un groupe de 2 marches d'un coup.
2- Le cas où on monte un seul jeu de 2 marches.
3- Le cas où on monte deux fois deux marches.

Dans le cas général le nombre de cas est donné par E(n/2).
Et pour chacun des cas tu as C(k,n-k) façons (ou k est un nombre de groupements de 2 marches franchis lors de la montée donné).

Ce qui conduit au résultat que je t'ai donné.

Si tu n'arrives pas à t'en convaincre essaie avec plein de cas particuliers et si ça ne passe toujours pas, attends les explications de ta prof.

Le nombre de cas est donné par E(n/2) + 1.
Coquille.

Il y a une méthode plus simple :

On appelle f(n) le nombre de possibilités pour monter un escalier à n marche

Pour monter un esalier une marche, la seule chose qu'on peut faire c'est monter une marche. Donc f(1) = 1.

Pour monter un escalier à deux marches on peut soit monter une fois deux marches ou monter deux fois une marche. Donc f(2) = 2.

Soit n un entier non nul, on veut monter n + 2 marches. Au départ on a lechoix entre monter une ou deux marches.

- Si on monte une marche, il reste n + 1 marches à monter, donc on a f(n + 1) possiblités.

- Si on monte de deux marches, il reste n marches à monter, donc on a f(n) possiblités.

On en déduit f(n + 2) = f(n) + f(n + 1).

En prenant par convention f(0) = 1. f est définie sur N par :

f(0) = 1
f(1) = 1
f(n + 2) = f(n) + f(n + 1)

Il s'agit donc de la suite de fibonacci.

On appelle u_n ce nombre recherché. Pour des petits escaliers, on sait résoudre le problème. Si l'escalier
a une marche, il n'y a qu'une façon de le gravir ; ainsi u_1 = 1. Si l'escalier a deux marches, il y a deux façons : soit on monte les deux marches à la fois, soit on y va pépère ; ainsi u_2 = 2.

Mettons-nous maintenant devant un escalier de n marches, avec n >= 3. Au bas de l'escalier, on a deux possibilités : soit on monte une marche, soit deux. Si on a monté une
marche, il nous restera évidemment n − 1 marches à gravir, sinon il nous en restera n − 2. De cela, on déduit la relation de récurrence suivante :

u_{n+2} = u_{n-1} + u_n

qui est la fameuse suite de Fibonacci. On peut montrer par récurrence que le nombre de manière de monter est donné par la formule : u_n = (A^{n+1} - B^{n+1})/(A - B), n >= 1

où A = (1 + V5)/2 et B = (1 - V5)/2

"Si on a monté une
marche, il nous restera évidemment n − 1 marches à gravir, sinon il nous en restera n − 2. De cela, on déduit la relation de récurrence suivante : "

<=>

"Si on a monté une marche, il nous restera évidemment n - 1 marches à gravir, sinon il nous en restera n - 2. De cela, on déduit la relation de récurrence suivante : "

"u_{n+2} = u_{n-1} + u_n "

Désolé, c'est plutôt : "u_{n+2} = u_{n+1} + u_n"

Wouah merci les gars, j'ai tout compris pour le coup C'est vraiment sympa

Merci pour les exemples MCWarrior, ça m'a bien aidé )