Mathématiques - deja posté par Zebelon

deja posté par Zebelon
(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)

Posted by: aviateurpilot

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?

Posted by: BancH

Avec $n>3$ , je trouve $n+\Large \sum_{k=1}^{n-4}1$ façons de monter l'escalier.

Posted by: aviateurpilot

coment ta fait?
moi aussi je ss entrain de chercher la solution.

Posted by: BancH

Ma solution porte seulement sur des observation, maintenant je recherche la démonstration.

Posted by: aviateurpilot

voila ce que je propose meme s'il es un peu imaginaire.

soit A l'operation suivante "1saut d'une marche"
et B "1saut de 2 marche"de tel sort qu'il ne soit pas pres d'un C
C "2sauts de de 2marches " de tel sort qu'il ne soit pas pres d'un B

on suppose que la grenouille a fait a fois A
et b fois B
et c fois C
dans ce cas a+2b+4c=n avec a>b et a>c
on dois denombrer le nombre de permutation d'un nombre donné des opération de A et B et C

imaginer avec moi a fois A.si on veux mettre b fois B et c fois C .on a (a+1) places
donc le nombre de cas de mettre les C c'est
(a+1)!/c!(a+1-c)!
et pour les B .on va les mettre dans les autres places
et prenant tt les valeur possibles de a,b et c on va surement trouver la solution

Posted by: BancH

Citation:

Posté par aviateurpilot

C "2sauts de de 2marches "

Elle ne peut pas enchaîner 2 sauts de 2 marches.

Posted by: aviateurpilot

il peux faire un saut de 2 marches et faire un autre saut de 2 marches

Posted by: BancH

Mais séparés par un saut d'un marche.

Posted by: aviateurpilot

ah j'ai oublier
dans ce cas ce probleme est plus simple que je pense

Posted by: aviateurpilot

alors quand on trouve la solution de

Citation:

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?

on va chercher la solution de

Citation:

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)2 fois successive , ç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?

Posted by: aviateurpilot

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 $\sum_{b=0}^{b_{max}} f(n-2b,b)$
avec $b_{max}=[n/3]+1$ si n=2 modulo 3
et $b_{max}=[n/3]$ si n=0 ou 1 modulo 3
car on arrive a $b_{max}$ si on a ce ordre B.A.B.A.B.A.....

Posted by: Alpha

Pourquoi poster une nouvelle discussion sur ce sujet puisque cela a déjà été fait par Zebulon dans la partie Enigmes?

Posted by: aviateurpilot

on va chercher maintenant ça:
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)2 fois successive , ç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?
""c'est different""

Posted by: Alpha

D'accord

Posted by: aviateurpilot

j'ai trouvé la solution du 1er
et j'ai presque trouvé le 2eme

Posted by: Patastronch

Comme alpha je capte pas pourquoi avoir créer un second sujet sur la meme enigme. Meme si tu en change l'ennoncé en page 2, ton poste initial est identique a celui de Zebulon.

Post de Zebulon :

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?

Le tien :

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?

A part le bonjour je vois pas la difference. D'autant plus que tu le savais puisque tu as posté dans le post de Zebulon avant de créer ce sujet. Serieusement y a un truc qui m'échappe.

Posted by: aviateurpilot

voila la difference

Citation:

Mais quand elle en a monté deux (en sautant une marche)2 fois successive

Posted by: aviateurpilot

banch .tu es dac avec moi pour la solution du 1er exo ou non?

Posted by: BancH

Nan, je ne comprends fichtre rien

Là je suis sur le second exo, je rédige ma réponse.

Posted by: aviateurpilot

tu n'a pas compris ce que j'ai fait alors?
quand tu trouve la solution du 2eme exo on parlera de ma demonstration
bon chance

Posted by: BancH

Voilà, j'ai une solution,mais ma démonstration est peut-être mal expliquée:

Un saut d'une marche est noté a, un saut de deux marches est noté b- deux sauts de deux marches suivis d'un saut d'une marche (dû aux crampes du crapaud) sont notés b-b-a

Les combinaisons de sauts sont:
avec n=1:
a
=> 1 combinaison

avec n=2:
On prend les combinaisons de n=2-1, auxquelles on ajoute a devant.
aa

On remplace les aa commençant une combinaison par b- si aa n'est pas suivi de b-b-
b-
=> 2 combinaisons

avec n=3:
On prend les combinaisons de n=3-1, auxquelles on ajoute a devant.
aaa
ab-

On remplace les aa commençant une combinaison par b- si aa n'est pas suivi de b-b-

b-a

=> 3 combinaisons

avec n=4:
aaaa
aab-
ab-a

b-aa
b-b-
=> 5 combinaisons

avec n=5:
aaaaa
aaab-
aab-a
ab-aa
ab-b-

b-aaa
b-ab-
b-b-a
=> 8 combinaisons

avec n=6:
aaaaaa
aaaab-
aaab-a
aab-aa
aab-b-
ab-aaa
ab-ab-
ab-b-a

b-aaaa
b-aab-
b-ab-a
b-b-aa
=> 12 combinaisons

A chaque fois que n augmente de 1, on prend:
n combinaisons
+ le nombre de combinaisons de n marches commençant par a qui est donc égal au nombre de combinaisons de $n-1$ marches
- le nombre de combinaisons de n marches commençant par ab-b-, soit 1 pour tout $n>4$ .

Avec $U_n$ le nombre de combinaisons avec n marches et $n>4$ , on a donc:

$\Large U_n=U_{n-1}+U_{n-2}-1 $

Et pour n<4: $ U_n=U_{n-1}+U_{n-2}$

Posted by: aviateurpilot

=>le nombre de combinaisons de n marches commençant par a qui est égal au nombre de combinaisons de n-1 marches

=> le nombre de combinaisons començant par "ba" est $U_{n-2}$

et puisque on n'a pas calculé le nombre de combinaisons començant par "bb"

alors normalement $U_n > U_{n-1}+U_{n-2}$
mais ta formule ne verifie pas ça

Posted by: aviateurpilot

n>4
il y a 3 possibilités
la combinaison ne peux comencer que par "a" ou bien "ba" ou bien "bba"
si $E_1$ ={les combinaisons començant par "a"}
$E_2$ ={les combinaisons començant par "ba"}
$E_3$ ={les combinaisons començant par "bba"}
E={tt les combinaisons possible}
alors $E_1 \cup E_2 \cup E_1=E$
et $E_1 \cap E_2 \cap E_1=\empty$

=>les combinaisons començant par "a" est $U_{n-1}$
=>les combinaisons començant par "ba" est $U_{n-2}$
=>les combinaisons començant par "bba" est $U_{n-3}$

donc $U_n=U_{n-1}+U_{n-2}+U_{n-3}$
t dac avec moi??

Posted by: BancH

Oui, j'avais pas pensé, alors l'égalité est:

$\Large U_n=U_{n-1}+U_{n-2}-U_{n-5} $

Pour tout $n\in \mathbb {N}$

Posted by: aviateurpilot

mais tu dois trouvé $U_n>U_{n-1}+U_{n-2}$
$U_n=U_{n-1}+U_{n-2}-U_{n-5}$ ne verifie pas ça

tu ne confirme pas ma formule $U_n=U_{n-1}+U_{n-2}+U_{n-3}$ ?
je l'ai fait en se basant par ta 1er methode

Posted by: BancH

Citation:

Posté par aviateurpilot

$U_n>U_{n-1}+U_{n-2}$

C'est ça qui est faux.
$U_{n-1}+U_{n-2}>U_n$ ou égal

Posted by: aviateurpilot

Citation:

=>le nombre de combinaisons de n marches commençant par a qui est égal au nombre de combinaisons de n-1 marches

=> le nombre de combinaisons començant par "ba" est $U_{n-2}$

et puisque on n'a pas calculé le nombre de combinaisons començant par "bb"

si on pose $V_n$ =nombre de combinaisons començant par "bb"

alors normalement $U_n=U_{n-1}+U_{n-2}+V_n$
et puisque $V_n>0$ alors $U_n>U_{n-1}+U_{n-2}$

ou es la faute?

Posted by: BancH

$U_n=U_{n-1}+U_{n-2}-V_n$

Posted by: aviateurpilot

Citation:

n>4
il y a 3 possibilités
la combinaison ne peux comencer que par "a" ou bien "ba" ou bien "bba"
si $E_1$ ={les combinaisons començant par "a"}
$E_2$ ={les combinaisons començant par "ba"}
$E_3$ ={les combinaisons començant par "bba"}
E={tt les combinaisons possible}
alors $E_1 \cup E_2 \cup E_1=E$
et $E_1 \cap E_2 \cap E_1=\empty$

=>les combinaisons començant par "a" est $U_{n-1}$
=>les combinaisons començant par "ba" est $U_{n-2}$
=>les combinaisons començant par "bba" est $U_{n-3}$

donc $U_n=U_{n-1}+U_{n-2}+U_{n-3}$

ou es la faute là?

Posted by: BancH

$U_n=U_{n-1}+U_{n-2}-U_{n-5}$

Je vais te montrer pourquoi $U_{n-5}$ dans quelques minutes.

Posted by: aviateurpilot

quand tu me montre pour koi $U_{n-5}$
montrer moi pour ça est faux:

Citation:

s'il est faux

Posted by: BancH

On cherche $V_n$ le nombre de combinaisons de n-2, commençant par b-b-

Pour n=6:
b-b-
=> $V_n=1$

Pour n=7:
b-b-a
=> $V_n=1$

Pour n=8:
b-b-aa
=> $V_n=1$

Pour n=9:
b-b-aaa
b-b-ab-
=> $V_n=2$

Pour n=10:
b-b-aaaa
b-b-ab-a
b-b-aab-
=> $V_n=3$

Pour n=11:
b-b-aaaaa
b-b-aaab-
b-b-aab-a
b-b-ab-b-
b-b-ab-aa
=> $V_n=5$

On retombe dans le cas précédent, on avait n=1, n=2... là on a n=6, n=7... avec les mêmes résultats.
Le nombre de combinaisons avec n-2 marches commençant par b-b- correspond au nombre de combinaisons totales de $n-6+1=n-5$ marches, soit $U_n-5$

Et il faut enlever ces $U_n-5$ combinaisons et non les ajouter car ce sont celles qui commencent par aab-b- où aa ne peut pas être remplacé par b-

P.S. la faut que j'aille me coucher, donc on verra ça demain.

Posted by: aviateurpilot

"bb" dois etre forcement suivé par "a"

Citation:

Mais quand elle en a monté deux (en sautant une marche)2 fois successive , ça lui file des crampes aux pattes donc elle ne monte qu'une marche au saut suivant.

et en plus j'ai dit que $V_n$ est le nombre de combinaisons de n commençant par bb
et il est facile de trouvé au moin 2 combinaisons de 6 commençant par bb
mais toi t'a dit:

Citation:

Pour n=6:
............
=> $V_6$ =1

apart tt ca si tu revois bien cette demonstration tu va voir qu'il es 100pourcent logique et il ne se base pas sur des exemples qui peux conduire a des fautes

Citation:

Posted by: aviateurpilot

bonne nuit et à demain BancH
merci pour tt

Posted by: BancH

Là où tu as faux: $E_1\cap E_2\cap E_3 = E_3$ car $E_3\subset E_2$

Pour le début de l'égalité, on est d'accord pour $U_n=U_{n-1}+U_{n-2}$ Cela représente toutes les combinaisons de n marches, or il faut exclure les combinaisons commençant par b-b-b-.

On note $C_n$ le nombre de combinaisons avec n marches, et l'on met le début des combinaisons entre parenthèses.

$C_n (b-b-b-) \Longleftrightarrow C_{n-1}(ab-b-) \Longleftrightarrow C_{n-2}(b-b-) \Longleftrightarrow C_{n-3}(ab-) \Longleftrightarrow C_{n-4}(b-) \Longleftrightarrow C_{n-5}(a) \Longleftrightarrow C_{n-6}$
Donc avec $n>6$ on a:

$\Large U_n=U_{n-1}+U_{n-2}-U_{n-6}$

Posted by: BancH

Mais c'est toujours faux car on a enlevé seulement les b-b-b- commençant les combinaisons, et pas les autres. Je trouve alors,
avec $q$ le quotient de la division euclidienne de $n-1$ par $5$ :

$\Large U_n=U_{n-1}+U_{n-2}-qU_{n-6}$

Posted by: yos

Pourquoi recommencez-vous ce problème? Il me semble qu'une solution a été donnée sur l'autre fil.
Les relations
$u_{n+4}=u_{n+2}+u_{n+1}+u_n$
et
$u_{n+3}=u_{n+2}+u_n$
sont toutes deux correctes il me semble. La première est une conséquence immédiate de la seconde et la seconde se justifie facilement en distinguant les deux façons suivantes de gravir n+3 marches :
-celles se terminant par 1 ( $u_{n+2}$ façons),
-celles se terminant par 2 et donc par 1,2 ( $u_n$ façons).
Si vous voyez une erreur dites le moi.
Mais peut-être cherchez-vous une formule explicite?

Posted by: BancH

Il y a une petite différence dans l'énoncé, dans celui de Zebulon, la grenouille avait une crampe lorqu'elle montait deux marches en un saut, là, c'est lorsqu'elle monte quatre marches en deux sauts de deux marches.

Posted by: yos

Ce n'est pas ce que j'avais saisi avec le premier message. Admettons.

Posted by: BancH

Oui, au départ c'était la même énigme que celle posté par Zebulon mais elle a changé au cours de la discussion.

Posted by: aviateurpilot

je je vai recomencer et correcter tous les fautes que j'ai fait:
A:1saut d'une marche
B:1saut de 2 marches
soit E={tt les combinaisons possible}
$E_1$ ={les combinaisons començant par "A"}
$E_2$ ={les combinaisons començant par "BA"}
$E_3$ ={les combinaisons començant par "BBA"}
il est clair que les combinaisons començant par "BBA" et totalement differente des combinaisons començant par "BA"
dans $E_2$ la 2eme action c'est "A" mais dans $E_3$ la 2eme action c'est "B"
donc ce que t'a dit est faux :

Citation:

car $E_3 \subset E_2$

il est meme clair que $E_1 \cup E_2 \cup E_1=E$
et $E_1 \cap E_2 \cap E_1=\empty$

=> dans $E_1$ il a fait "A" et il lui rest n-1 marches dont le nombre de possibilité est $U_{n-1}$
=> dans $E_2$ il a fait "BA" et il lui rest n-3 marches dont le nombre de possibilité est $U_{n-3}$
=> dans $E_3$ il a fait "BBA" et il lui rest n-5 marches dont le nombre de possibilité est $U_{n-5}$

et puisque $E_1 \cup E_2 \cup E_1=E$
et $E_1 \cap E_2 \cap E_1=\empty$
alors:
$U_n=U_{n-1}+U_{n-3}+U_{n-5}$

stp BANCH donne moi un raisonement mathématique pour chaque faute que tu remarque. je vai aller manger queque chose et je revien

Posted by: BancH

Oui ça à l'air bon sauf que tu as oublié quelque chose:

Les crampes !!

Tu n'as comptabilisé que les crampes dûes aux 4 premiers sauts.

Je pense que ma formule est bonne:

Citation:

Posté par BancH

avec $q$ le quotient de la division euclidienne de $n-1$ par $5$ :

$\Large U_n=U_{n-1}+U_{n-2}-qU_{n-6}$

Posted by: aviateurpilot

dans moi alors un debut d'une combinaison qui ne comence ni par "A" ni "BA"
ni "BBA" ........?

Posted by: BancH

Citation:

Posté par aviateurpilot

dans moi alors un debut d'une combinaison qui ne comence ni par "A" ni "BA"
ni "BBA" ........?

Je ne comprends pas ce que tu veux dire.

Ta formule à toi admet la combinaisons suivante:

aaaaaaab-ab-aaab-aaab-b-aab-b-b-b-b-b-b-b-b-b-b-b-b-b-b-b-b-b-b-b-

Donc elle est fausse.

Posted by: aviateurpilot

mais quand j'ai dit $E_1$ ={le nombre de combinaisons començent par "A"} je parle seulement des combinaisons possibles

Posted by: BancH

Ah oui, ta formule semble fonctionner, je pensais qu'elle était fausse à cause d'un erreur de calcul.

Posted by: aviateurpilot

ok

mais cette methode là est basée sur ta methode
j'ai utilisé ta remarque en travaillant par le debut des combinaisons
c'est plus facile que travailler par la fin des combinaisons

mais il ne reste à calculer le nombre de possibilités en fonction de n

Posted by: BancH

En développant $\Large U_n=U_{n-1}+U_{n-3}+U_{n-5}$ peut-être.

Posted by: aviateurpilot

oui c ce que j'ai dit

maintenant on doit calculer $U_n$ en fonction de n

Posted by: hero_h_2zef

salu tt le monde : la réponse à la première énigme est : 1 + (n-1) + C(2,(n-1)) + C(3,(n-1))
+.... + C( [ (n + 1) / 3 ] , (n-1) ) .
La grenouille peut en effet sauter 0 fois deux marches ou 1 fois deux marches ( elle a alors (n-1) marches possibles pour ce faire , étant donné qu'elle ne peut pas sauter deux marches sur l'avant dernière marche ou sur la dernière mais sur
la 0 ème on peut ) ou 2 fois deux marches ... jusqu'au nombre total de " doubles sauts " possibles c'est-à-dire [ (n + 1) /3 ] : on le montre en effet par récurrence en ininisialisant pour n = 2 ( on bien un saut de deux marches possible ) et en remarquant que ce nombre augmente tous les trois escaliers .