Grenouille (énigme pour Terminale)

par **Zebulon** » 05 Juin 2006, 14:41

C'est bizarre, j'avais l'impression que ce problème était facile mais en fait... il est plus compliqué qu'il en a l'air...
Je me suis trompée. Je vérifie pour la solution de Alpha.

par **Zebulon** » 05 Juin 2006, 14:58

Alpha et moi avons fait la même chose et malheureusement je crois qu'on s'est trompé tous les deux.
D'après un arbre,

,

mais

ce qui ne va pas avec

.

par **Zebulon** » 05 Juin 2006, 15:44

Pardon Alpha, je me suis pris la tête pour rien!!! Tu as raison : la grenouille s'écrase si elle fait un bond de 2 alors qu'elle est en n-1 et que l'escalier comporte n marche.
Merci, c'était mon fou rire de la journée!

par **yos** » 05 Juin 2006, 20:28

Bonsoir.
Je comprends pas.
Je trouve 1,2,3,4,6 pour les premières valeurs. On est loin de Fibo.
Ou est passée la consigne :
"jamais deux sauts de deux marches consécutifs"??

par **yos** » 05 Juin 2006, 20:35

L'examen des premières valeurs donne

.
Si c'est ça, faudrait le justifier dans le cas général.

par **Patastronch** » 05 Juin 2006, 20:47

Bon une autre idée :

j'appelle :
un saut de type A: un saut de 2 cases suivit d'un saut d'une case.

un saut de type B: un saut d'une case suivit d'un saut de 2 cases.
un saut de type C: un saut d'une case.

Pour N marches on peut avoir i sauts de types A ou B et N-3i sauts de type C avec

On tombe alors dans un probleme ou il suffit de sommer les combinaisons possibles :

pour i=0 : on a

possibilités
pour i=1 : on a

possibilités
pour i=2 : on a

possibilités
...

on a :

D'ou la somme finale :

J'ai la flem de simplifier mais je pense que cette fois cest bon.

par **bitonio** » 05 Juin 2006, 21:04

pas si simple que ca pour un terminal averti ^^ Je comprend vos raisonement, mais j'aurai jamais réussi seul à trouver ca...

par **Patastronch** » 05 Juin 2006, 21:30

ma solution est fausse j'ai oublié d'interdire la succession : BA.

Par contre ne prenant :

Saut de type A : un saut de 2 suivi d 'un saut de 1
Saut de type B : un saut de 1

et en résolvant le probleme a N-1 marches et N-2 marches on a notre solution a notre probleme a N marches qui vaut la somme des deux solutions précédantes. Il faut faire ainsi car le dernier saut peut etre un saut de 2, donc en résolvant le probleme a N-1 marche en fixant le dernier saut a un saut de 1 et le probleme a N-2 marches en fixant le dernier saut a un saut de 2.

On fait une somme des combinaisons toute simple maintenant et on a notre résultat. J'ai un peu la flem de faire les calculs je les ferais demain.
Bonne soirée a tous.

par **Alpha** » 05 Juin 2006, 22:35

Salut, en quoi ma solution ne vous satisfait-elle pas? Pouvez-vous m'indiquer à quel endroit vous n'êtes pas d'accord avec mon raisonnement? Par ailleurs, ma solution tient tout à fait compte de la consigne "jamais deux sauts de 2 marches consécutifs"...

par **yos** » 05 Juin 2006, 22:37

Mieux :

.
Parmi les façons de gravir de n+3 marches, il y a :
-celles se terminant par 2 (et donc par 12 : il y en a

);
-celles se terminant par 1 (il y en a

).
D'où la relation de récurrence.
Pour trouver une formule explicite, il faudrait les racines de

.

par **Alpha** » 05 Juin 2006, 22:41

Je m'explique : quand j'écris que V(n+1) = U(n-1), je tiens compte du fait qu'en finissant par un saut de 2 marches, je ne pouvais être arrivé en n-1 qu'en finissant par un saut de 1 marche. Pour l'instant je suis assez convaincu par mon raisonnement... S'il est faux, ça serait sympa de m'indiquer où est l'erreur...

Merci.

par **Patastronch** » 05 Juin 2006, 22:58

Alpha ta solution est juste c'est évident, si je poste une autre facon de faire c'est juste pour me contraindre a utiliser que des outils de terminal pour trouver la formule en fonction de n. Quant à yos il tombe sur la meme suite finale que toi si je ne m'abuse mais avec un raisonnement plus simple.

par **Zebulon** » 06 Juin 2006, 09:27

yos a écrit:Mieux : .
Parmi les façons de gravir de n+3 marches, il y a :
-celles se terminant par 2 (et donc par 12 : il y en a );
-celles se terminant par 1 (il y en a ).
D'où la relation de récurrence.
Pour trouver une formule explicite, il faudrait les racines de .

C'est aussi ce à quoi j'avais pensé quand je me suis pris la tête. Mais c'est en considérant que la grenouille peut sauter deux marches alors qu'elle est à la (n-1)-ième marche.

par **Zebulon** » 06 Juin 2006, 12:16

On peut également utiliser les séries génératrices (c'est ce que je fais quand j'ai une relation de récurrence) pour déterminer une solution explicite.

par **yos** » 06 Juin 2006, 17:31

Zebulon a écrit:C'est aussi ce à quoi j'avais pensé quand je me suis pris la tête. Mais c'est en considérant que la grenouille peut sauter deux marches alors qu'elle est à la (n-1)-ième marche.

Ben il me semble que je prends cet aspect en compte. Qu'est ce qui ne te va pas dans la justification? J'ai partitionné l'ensemble des "montées" de n+3 marches en deux sous-ensembles lesquels sont respectivement en bijection avec les ensembles de montées de n et n+2 marches En tout cas ma formule marche (ainsi que la précédente

qui est une conséquence immédiate de l'autre) pour les premières valeurs que j'ai calculées directement

par **Alpha** » 06 Juin 2006, 20:02

yos a écrit:En tout cas ma formule marche (ainsi que la précédente qui est une conséquence immédiate de l'autre) pour les premières valeurs que j'ai calculées directement

Salut!

Euh... personnellement ton raisonnement, yos, me semble un peu rapide, car on ne voit pas bien où tu tiens compte de la règle : Deux sauts de 2 marches ne doivent jamais se succéder. Mon raisonnement en tient clairement compte. Le fait que ça marche pour les 1ères valeurs n'est nullement un argument.

Cordialement, Alpha

par **Patastronch** » 06 Juin 2006, 20:14

Alpha a écrit:Salut!

Euh... personnellement ton raisonnement, yos, me semble un peu rapide, car on ne voit pas bien où tu tiens compte de la règle : Deux sauts de 2 marches ne doivent jamais se succéder. Mon raisonnement en tient clairement compte. Le fait que ça marche pour les 1ères valeurs n'est nullement un argument.

Cordialement, Alpha

Il en tiens compte en considérant les saut de +3 marches.

Au final c est la meme suite que la tienne si tu regardes bien d'ailleur, il a juste racourci les étapes en feintant.

par **Alpha** » 06 Juin 2006, 21:17

Bien vu, Patastronch! :lol4:

par **aviateurpilot** » 12 Juin 2006, 20:49

si j'ai pas fait d'erreur
voila la solution de 1er exo:
soit A l'operation suivante "1saut d'une marche"
et B "1saut de 2 marche"de tel sort qu'elle ne soit pas pres d'une autre operation B

on suppose que la grenouille a fait a fois A
et b fois B

dans ce cas a+2b=n avec a>ou=b
on dois denombrer le nombre de permutation d'un nombre donné des opération de A et B

imaginer avec moi a fois A.si on veux mettre b fois B .on a (a+1) places
pace qu'on peux pas mettre deux B l'un pres de l'autre.
le nombre de cas est: f(a,b)=(a+1)!/{b!(a+1-b)!}

il nous rest que faite la somme des f(a,b) pour tt les valeur possible de a et b
f(a,b)=f(n-2b,b)
donc le nombre de cas possibles est

avec

si n=2 modulo 3
et

si n=0 ou 1 modulo 3
car on arrive a

si on a ce ordre B.A.B.A.B.A.....

par **aviateurpilot** » 12 Juin 2006, 21:38

donc c'est 2^(n+2) -2^([n/4]+1)

Grenouille (énigme pour Terminale)

Qui est en ligne