Grenouille (énigme pour Terminale)

par **Zebulon** » 05 Juin 2006, 06:26

Bonjour,
voici une petite énigme pour Terminale :
Une grenouille veut gravir un escalier de n marches. Elle monte les marches soit par une, soit par deux. Mais quand elle en a monté deux (en sautant une marche), ça lui file des crampes aux pattes donc elle ne monte qu'une marche au saut suivant.
De combien de façons la grenouille peut-elle gravir l'escalier?

par **Mikou** » 05 Juin 2006, 12:15

est ce que lorsquelle est sur la marche n-1 et si elle a la possibilité de faire un saut de deux alors on considere que cela a le meme resultat qu'un saut simple ?

par **Mikou** » 05 Juin 2006, 12:33

on va supposer que si il est a la marche n-1 il doit faire un saut de 1

par **Patastronch** » 05 Juin 2006, 13:03

E(i=0 a n/2)(C(i,n-i))

avec E le sigma de somme, et C(x,y) les combinaisons de x parmis y.

explications :

type a : saut de une marche
type b : saut de 2 marches

on cherche a placer zero saut de type b parmis les n sauts de types a: on a donc C(0,n) possibilités
on cherche a placer un saut de type b parmis les n-2 sauts de types a: on a donc C(1,n-1) possibilités
.
.
.
on cherche a placer i saut de type b parmis les n-2i sauts de types a: on a donc C(i,n-i) possibilités
.
.
.
on cherche a placer n/2 sauts de type b parmis les 0 saut de types a: on a donc C(n/2,n/2) possibilités

on somme le tout d'ou :

E(i=0 a n/2)(C(i,n-i)).
J'ai pas le temps la de regarder si ca se simplifie, si personne reprend le truc j regarderai plus tard.

par **Mikou** » 05 Juin 2006, 13:06

lol je trouve plus compliqué que ca encore : somme, factoriel, partie entiere et combinaison ... ca me parait bien etrange :ptdr:
A noté que sur n marche au maximum la grenouille peut faire

sauts de deux marches

par **Zebulon** » 05 Juin 2006, 13:07

Patastronch a écrit:a placer i saut de type b parmis les n-2i sauts de types a: on a donc C(i,n-i) possibilités.

Vous voulez sûrement dire i sauts de type b parmi (ça s'écrit sans s!!!) les n sauts, ce qui fait n-2i sauts de type a.
Cherchez une solution plus simple à l'aide d'une relation de récurrence.
De plus vous allez jusqu'à n/2 mais rien ne dit que n est pair.

par **Alpha** » 05 Juin 2006, 13:18

Bon, j'ai déjà donné ma solution à Zeb par msn, mais je la redonne : on note Un le nombre cherché quand il y a n marches, regardons ce qui se passe pour n+1 marches : soit la grenouille arrive à la dernière marche par un saut d'une marche, et avait Un façons de gravir les marches précédentes, soit par un saut de 2 marches, et on a U(n-1) façons, Donc U(n+1) = Un + U(n-1) : Fibonacci : on regarde les 3 premiers rangs et c'est fini... :lol4:

par **scelerat** » 05 Juin 2006, 13:19

Je commencerais par considerer les manieres N(m) dont on peut ecrire n sous la forme 2m+p.
Ensuite, pour chacun de ces couples (m,p), de combien de manieres A (m,p) peut on ranger les m 2 et les p 1 en n'ayant jamais deux 2 consecutifs ?
Une sequence se termine par 2 ou par 1.
Si elle se termine par 2, elle se termine par 1,2 et il nous reste A(m-1,p-1) manieres de ranger les m+p-2 valeurs precedentes. Si elle se termine par 1, il nous reste A(m,p-1) manieres de ranger les m+p-1 valeurs precedentes.
La suite est laissee au lecteur.

par **Patastronch** » 05 Juin 2006, 13:19

Zebulon a écrit:Vous voulez sûrement dire i sauts de type b parmi (ça s'écrit sans s!!!) les n-i sauts, ce qui fait n-2i sauts de type a.

rajoute ce qui est en gras et je susi d'acor,d mais c est un détail tu dis la meme chose que moi non ?

Zebulon a écrit:Cherchez une solution plus simple à l'aide d'une relation de récurrence.
De plus vous allez jusqu'à n/2 mais rien ne dit que n est pair.

Bon tas compris le principe non ? en gros si c est impair tu t'arretes a (n-1)/2. en fait tu vas jusqu'a E(n/2) où E() est la partie entiere.
C est pas une démonstration, je me suis pas amusé a matter tous les détails,ce que j 'ai fait c est juste une aproche intuitive du résultat, par contre si tu trouves ca compliqué je vois mal comment on peut faire plus vulgarisé , je trouve ca meme limite naif comme méthode :s

edit pour alpha : pas mal la suite de fibonacci, simple mais fallait y penser.

Mikou a écrit:l
A noté que sur n marche au maximum la grenouille peut faire sauts de deux marches

euh ca te suffit pas de dire que le nombre maximum de sauts de 2 marches pour n marches vaut E(n/2) ?

par **Alpha** » 05 Juin 2006, 13:26

J'ai répondu, la solution est très simple, mais j'ai supprimé logiquement mon message car après tout c'est mieux de vous laisser chercher encore un peu.

par **Mikou** » 05 Juin 2006, 13:31

Patastronch a écrit:
euh ca te suffit pas de dire que le nombre maximum de sauts de 2 marches pour n marches vaut E(n/2) ?

non c'est faux...

par **Zebulon** » 05 Juin 2006, 13:33

Merci Alpha de laisser chercher les autres :we: .
Tu auras le privilège de rerédiger la réponse si personne ne trouve (interdit entre autres à Alben, à Quidam et à Yos :++:).

par **Patastronch** » 05 Juin 2006, 13:34

Mikou a écrit:non c'est faux...

??? ah ? je comprends pas pourquoi, j'ai peut etre la tete dans le cul mais la je vois vraiment pas.

par **Mikou** » 05 Juin 2006, 13:34

trop tard jai vu la solution :) mais je persiste dans ma propre solution

par **Mikou** » 05 Juin 2006, 13:37

Patastronch a écrit:??? ah ? je comprends pas pourquoi, j'ai peut etre la tete dans le cul mais la je vois vraiment pas.

avec 7 ta solution donne 3 sauts possibles, or la bonne solution est 2, laquelle est bien donnée par 'ma' forumule

par **scelerat** » 05 Juin 2006, 13:37

Alpha a écrit:J'ai répondu, la solution est très simple, mais j'ai supprimé logiquement mon message car après tout c'est mieux de vous laisser chercher encore un peu.

J'ai eu le temps de voir ton message, et il m'a justement semble un peu rapide :zen:
On ne peut pas faire un saut de deux marches en dernier si on est arrive a la marche n-2 par un saut de deux marches...

par **Patastronch** » 05 Juin 2006, 13:39

Mikou a écrit:avec 7 ta solution donne 3 sauts possibles, or la bonne solution est 2, laquelle est bien donnée par 'ma' forumule

Ah je me suis planté, j'ai mal lu l'énoncé et j'avais pas vu qu'un saut de 2 marches était forcément suivit par un saut de une marche. Ma résolution est bien entendu fausse alors.

par **Alpha** » 05 Juin 2006, 13:45

scelerat a écrit:J'ai eu le temps de voir ton message, et il m'a justement semble un peu rapide :zen:
On ne peut pas faire un saut de deux marches en dernier si on est arrive a la marche n-2 par un saut de deux marches...

Exact! Il faut apporter une légère modification. Il faut distinguer entre les courses se finissant par un saut de deux marches et celles se finissant par un saut d'une marche... Les moyens mis en oeuvres sont identiques... Mais je n'en dis pas plus...

par **Mikou** » 05 Juin 2006, 13:45

! et bien sinon la solution serait extrement simple en utilisant des sommes avec des combinaison, dailleurs on pourrait simplifié je pense :happy3:

par **Alpha** » 05 Juin 2006, 13:58

Allez, après avoir revu ma copie, je donne ma réponse :

Soit Un le nombre de façon de gravir n marches en finissant par un saut d'une marche, Vn le nombre de façons de gravir n marches en finissant par un saut de 2 marches.

On a clairement U(n+1) = Un + Vn,
et V(n+1) = U(n-1).

Donc U(n+2) = U(n+1) + Un : Fibonacci! On résout Un, on en déduit Vn, et on trouve la solution qui est Wn = Un + Vn = Un + U(n-2).

J'espère ne pas m'être trompé cette fois.

Grenouille (énigme pour Terminale)

Grenouille (énigme pour Terminale)

Qui est en ligne