Défi sup (ECS-MPSI-...) : Saccharine la grenouille !

[Kikoo <3 Bieber]

Non non, je ne me moque pas de toi

Voilà un défi (qui porte bien son nom) destiné à Saccharine et à tout envieux de faire ses griffes en analyse combinatoire !
Attention c'est pas facile !

Une grenouille doit monter un escalier de n marches.
Elle peut effectuer des bonds pour franchir 1 ou 2 marches à chaque fois.
De combien de façons peut-elle arriver au sommet de l'escalier ?

[Anonyme]

Encore une fois, ce n'est pas de mon niveau Kikoo ! :ptdr:

Bon je vais chercher un brouillon et voir si j'y arrive quand même.

[Zweig]

Salut,

Cela revient (entre autre) à déterminer , le nombre de parties de {1, ..., n} ne contenant pas d'entiers consécutifs. Il se trouve que vérifie

[chan79]

Non non, je ne me moque pas de toi

Voilà un défi (qui porte bien son nom) destiné à Saccharine et à tout envieux de faire ses griffes en analyse combinatoire !
Attention c'est pas facile !

Salut
si f(n) est le nombre de façons d'arriver à la marche n, f(n)=f(n-1)+f(n-2)
on tombe sur la suite de Fibonacci
1, 2,3,5,8,...
f(n)=

[acoustica]

Non non, je ne me moque pas de toi

Voilà un défi (qui porte bien son nom) destiné à Saccharine et à tout envieux de faire ses griffes en analyse combinatoire !
Attention c'est pas facile !

Fibonacci power ^^

[acoustica]

Non non, je ne me moque pas de toi

Voilà un défi (qui porte bien son nom) destiné à Saccharine et à tout envieux de faire ses griffes en analyse combinatoire !
Attention c'est pas facile !

Fibonacci power ^^

C'est d'ailleurs un exemple intéressant pour expliquer que ce nombre un peu étrange est bel est bien un entier.

[Anonyme]

Dernière fois que tu me donnes un défi comme celui-ci Kikoo, qui n'est pas entièrement faisable à mon niveau...

Alors, voici ce que j'ai trouvé :
On a deux cas : lorsque le nombre de marche de l'escalier n est pair, et lorsqu'il est impair.

Donc la grenouille a (n/2)+1 possibilités de gravir les marches de l'escalier lorsque le nombre de marches n est pair.
Ainsi qu'elle a (n+1)/2 possibilités de gravir les marches de l'escalier lorsque le nombre n de marches est impair.

Maintenant, à toi de le démontrer par récurrence, si c'est juste ce que j'ai ! Moi je ne peux pas le faire puisque ce n'est pas de mon niveau...

Voilà ce que j'ai trouvé moi !
Je ne connais pas Fibonacci moi :triste:

[acoustica]

Dernière fois que tu me donnes un défi comme celui-ci Kikoo, qui n'est pas entièrement faisable à mon niveau...

Alors, voici ce que j'ai trouvé :
On a deux cas : lorsque le nombre de marche de l'escalier n est pair, et lorsqu'il est impair.

Donc la grenouille a (n/2)+1 possibilités de gravir les marches de l'escalier lorsque le nombre de marches n est pair.
Ainsi qu'elle a (n+1)/2 possibilités de gravir les marches de l'escalier lorsque le nombre n de marches est impair.

Maintenant, à toi de le démontrer par récurrence, si c'est juste ce que j'ai ! Moi je ne peux pas le faire puisque ce n'est pas de mon niveau...

Voilà ce que j'ai trouvé moi !
Je ne connais pas Fibonacci moi :triste:

La clé du problème réside dans le fait que lorsqu'on rajoute une marche, le nombre de façons d'y arriver est égal au nombre de façons d'arriver à la précédante + le nombre de façons d'arriver à celle de deux marches plus tôt. En effet, soit on arrive à la dernière marche en un saut, soit en un double-saut. C'est-à-dire qu'on se ramène à des problèmes déjà traités, et disjoints puisqu'ils diffèrent au moins du dernier saut. Autrement dit, on a une suite u(n+2)=u(n+1)+u(n), qui est la suite de Fibonacci. Sa résolution donne ce que Chan a dit. =)

[Anonyme]

La clé du problème réside dans le fait que lorsqu'on rajoute une marche, le nombre de façons d'y arriver est égal au nombre de façons d'arriver à la précédante + le nombre de façons d'arriver à celle de deux marches plus tôt. En effet, soit on arrive à la dernière marche en un saut, soit en un double-saut. C'est-à-dire qu'on se ramène à des problèmes déjà traités, et disjoints puisqu'ils diffèrent au moins du dernier saut. Autrement dit, on a une suite u(n+2)=u(n+1)+u(n), qui est la suite de Fibonacci. Sa résolution donne ce que Chan a dit. =)

Bonsoir Acoustica,

Merci pour cette reponse, je vois mieux desormais ce qu'est la suite de Fibonacci
Je n'en avais jamais entendu parler ! Est-ce au programme des terminales ES ou c'est vu dans le superieur (plutot filière S) ?

[chan79]

Bonsoir Acoustica,

Merci pour cette reponse, je vois mieux desormais ce qu'est la suite de Fibonacci
Je n'en avais jamais entendu parler ! Est-ce au programme des terminales ES ou c'est vu dans le superieur (plutot filière S) ?

Et si c'était une grenouille sportive qui peut franchir à chaque fois 1, 2 ou 3 marches, de combien de façons peut-elle atteindre la 20 ième marche ?

[acoustica]

Et si c'était une grenouille sportive qui peut franchir à chaque fois 1, 2 ou 3 marches, de combien de façons peut-elle atteindre la 20 ième marche ?

XD j'avais hésité à la poser cette question^^. La résolution ne laisse pas de problème particulier puisqu'on a un polynôme symétrique, mais ça devient un vrai de vrai comme défi ! =)
Mais en effet, c'est un peu dur en terminale. Enfin je ne vois pas comment expliciter la suite sans avoir vu les suites récurrentes. Ou alors Saccharine, tu peux prendre la formule de Chan73 et la démontrer par récurrence.

[acoustica]

Bonsoir Acoustica,

Merci pour cette reponse, je vois mieux desormais ce qu'est la suite de Fibonacci
Je n'en avais jamais entendu parler ! Est-ce au programme des terminales ES ou c'est vu dans le superieur (plutot filière S) ?

Disons que ce n'est pas vraiment au programme de quoi que ce soit je pense. Ca fait partie des choses qu'on croise souvent et qu'il est bon de connaître. Tu n'auras jamais un cours sur la suite de Fibonacci, mais tu la retrouvera souvent, parfois de façon inattendue comme dans ce défi.
C'est un peu comme les nombres de Catalan, les intégrales de Wallis (mon imagination et mes connaissances sont limitées^^), on les croise souvent au cours des études supérieures, c'est bon à connaître. Mais pour répondre à ta question, c'est vu dans le supérieur.

[Anonyme]

Bonjour,

Merci pour ta reponse acoustica ;)

Chan79, ce que tu proposes n'est pas mal du tout, mais je n'ai pas vraiment de temps à consacrer pour le faire... Je reprends les cours lundi, et j'ai d'autres devoirs qui m'attendent, donc voilà.
Mais j'essaierai de le faire lorsque je trouverai un peu de temps ;)

[chan79]

Bonjour,

Merci pour ta reponse acoustica

Chan79, ce que tu proposes n'est pas mal du tout, mais je n'ai pas vraiment de temps à consacrer pour le faire... Je reprends les cours lundi, et j'ai d'autres devoirs qui m'attendent, donc voilà.
Mais j'essaierai de le faire lorsque je trouverai un peu de temps

Ok c'est juste posé comme ça ...
Je précise bien que la question est posée uniquement pour 20 marches.

[acoustica]

Ok c'est juste posé comme ça ...
Je précise bien que la question est posée uniquement pour 20 marches.

Ah oui je vois. Alors effectivement, on peut le faire par calcul des termes les uns après les autres. Mais c'est dommage de se restreindre à n=20, c'est intéressant de la poser dans le cas général.

[chan79]

Ah oui je vois. Alors effectivement, on peut le faire par calcul des termes les uns après les autres. Mais c'est dommage de se restreindre à n=20, c'est intéressant de la poser dans le cas général.

oui, pour n=20, c'est fait en quelques secondes avec un tableur
pour n quelconque, le moins qu'on puisse dire, c'est qu'il y a du calcul ...
il faut commencer par résoudre x³-x²-x-1=0 (une racine réelle et deux complexes)