Enigme Dénombrement : grenouille et escalier 1/2 @ Prise2Tete

gabrielduflot · #1

Une grenouille doit monter un escalier de 20 marches. Elle ne peut monter qu'une marche ou deux marches à la fois.

Combien de possibilités différentes a-t-elle de monter cet escalier ?

kosmogol · #2

"un certain nombre"

soit pas loin de 10 946 possibilités si je ne me suis pas trompé !

pour n marches :
- on commence par 1 marche, on retrouve le calcul pour n-1 marches
- on commence par 2 marches, on retrouve le calcul pour n-2 marches

1 marche 1 possibilité
2 marches 2 possibilités
3 marches 3 possibilités
4 5
5 8
etc.

celina58 · #3

Elle a 2 possibilités

Soit elle saute 2 marches
Soit elle saute 1 marche

EfCeBa · #4

Je sais que je me suis surement compliqué la chose puisque je trouve
[latex]\sum_{i=0}^{10}{\binom{10+i}{2i}}=10946[/latex], nombre de Fibonacci (ce qui me fait dire qu'il doit y avoir plus simple)

Une petite vérification :
2,2,2,2,2,2,2,2,2,2 => 1
2,2,2,2,2,2,2,2,2,1,1 => 2 parmi 11 = 55
2,2,2,2,2,2,2,2,1,1,1,1 => 4 parmi 12 = 495
2,2,2,2,2,2,2,1,1,1,1,1,1 => 6 parmi 13 = 1716
2,2,2,2,2,2,1,1,1,1,1,1,1,1 => 6 parmi 14 = 3003
2,2,2,2,2,1,1,1,1,1,1,1,1,1,1 => 5 parmi 15 = 3003
2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1 => 4 parmi 16 = 1820
2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1 => 3 parmi 17 = 680
2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 => 2 parmi 18 = 153
2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 => 1 parmi 19 = 19
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 => 1
1+55+495+1716+3003+3003+1820+680+153+19+1 = 10946.

Nicouj · #5

Ça sent Fibonacci à plein nez :-p

Alors si il y a une marche il y a une façon de monter : [latex]U_1=1[/latex]
Si il y a 2 marches alors il y a deux façons : 2 marches d'un coup ou deux fois une marche : [latex]U_2=2[/latex]
Si il y a n marches avec [latex]n>2[/latex] alors soit la grenouille monte une marche et il reste toutes les posssibilités pour monter [latex]n-1[/latex] marches soit elle en monte deux et il reste toutes les possiblités pour monter [latex]n-2[/latex] marches :
[TeX]U_n=U_{n-1}+U_{n-2}[/latex].

on calcule [latex]U_{20}[/latex] :
[latex]
U_1=1
U_2=2
U_3=U_1+U_2 = 3
U_4=U_2+U_3 = 5
...
U_{20}=10946
[/TeX]

dhrm77 · #6

Le nombre de combinaisons est apparement donné par la suite de Fibonacci,
Donc pour 20 marches je dirais : 10946.
pour 1 à 20 marches :
1 - 1
2 - 2
3 - 3
4 - 5
5 - 8
6 - 13
7 - 21
8 - 34
9 - 55
10 - 89
11 - 144
12 - 233
13 - 377
14 - 610
15 - 987
16 - 1597
17 - 2584
18 - 4181
19 - 6765
20 - 10946

MthS-MlndN · #7

En 10 mouvements : une possibilité.

En 11 mouvements (deux fois 1 marche, neuf fois 2 marches) :
[TeX]C^{11}_2 = \frac{110}{2} = 55[/latex] façons de placer les deux petits sauts parmi 11.

En 12 mouvements (quatre fois 1 marche, huit fois 2 marches) :
[latex]C^{12}_4 = \frac{12 !}{8 ! \times 4 !} = \frac{11880}{24} = 495[/latex] façons de placer quatre mouvements parmi 12. (après modif)

En 13 mouvements (6 fois 1, 7 fois 2) :
[latex]C^{13}_6 = 1716[/latex] façons.

En 14 mouvements (8 fois 1, 6 fois 2) :
[latex]C^{14}_6 = 3003[/latex] façons.

En 15 mouvements :
[latex]C^{15}_5 = 3003[/latex] façons.

En 16, 17, 18, 19, 20 mouvements respectivement :
[latex]C^{16}_4 = 1820[/TeX]
[TeX]C^{17}_3 = 680[/TeX]
[TeX]C^{18}_2 = 153[/TeX]
[TeX]C^{19}_1 = 19[/TeX]
[TeX]C^{20}_0 = 1[/TeX]
On somme le tout : [latex]1+55+495+1716+3003+3003+1820+680+153+19+1=10946[/latex]

Donc, si je ne me suis trompé nulle part après relecture et MPGDF, notre grenouille a 10946 façons différentes de monter cet escalier. Si je ne me suis trompé nulle part.

evariste · #8

10 946

=c(10,0)+c(11,2)+c(12,4)+c(13,6)+c(14,8)+c(15,10)+c(16,12)+c(17,14)+c(18,16)+c(19,18)+c(20,20)

Antonio0034 · #9

Salut,

Pour aller à la première marche, la Grenouille n'a qu'une seule solution : Un saut simple (1 solution).
Pour la seconde marche, elle a deux solutions : Un saut double ou deux sauts simples (2 solutions).
Pour la troisième marche, un simple un simple et un simple, ou un simple et un double, ou un double et un simple (3 solutions).
Pour la quatrième : 1 1 1 1 ou 1 1 2 ou 1 2 1 ou 2 1 1 ou 2 2 (5 solutions) et ainsi de suite.

On Remarque donc qu'à chaque étape le nombre de solution des étapes précédentes s'additionne pour donner le bon nombre.

Ce qui nous pousse vers une suite de Fibonacci :

1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711

J'ai volontairement laissé 21 étapes à la suite, car je penche vers deux solutions différentes :

La première a 20 étapes et lorsqu'on arrive pile à la 20eme marche : 10946 façons différentes de monter les marches.

La seconde a 21 étapes et lorsqu'on arrive à la 19eme marche on peut se permettre de faire un saut double (bien que seulement la moitié du saut soit nécessaire pour arriver au sommet): 17771 façons différentes de monter les marches.

Voila, merci en tout cas pour cette énigme passionnante.

Kikuchi · #10

Si elle ne fait que 10 doubles sauts (et donc 0 simples sauts) -> 1 possibilité
Si elle n'en fait que 9, il lui reste 2 simples sauts à faire : 2 sauts à placer sur 20 marches -> C(20,2) -> 190 possibilités
Si elle n'en fait que 8, il lui reste 4 simples sauts -> C(20,4) -> 4.845

Bref en gros, la somme des C(20,k) pour k pair -> 524.288

Ca semble faire un peu beaucoup, je suis pas très sûr de moi

Bamby · #11

elle fera entre 10 et 20 saut, reste plus qu'a calculer le nombre de possibilité pour chacun des 11 cas.

20: 20 simple 0 double : 1
19: 18 simple 1 double : 19
18: 16 simple 2 double : 18*17 / 2 = 153
17: 14 simple 3 double : 17*16*15 / 3*2 = 680
de même façon :
16: 1820
15: 3003
14: 3003
13: 1716
12: 495
11: 55
10: 1

total : 10946, ça fait plus que ce qu'on pourrais croire a priori.

Praem · #12

Salut, je suis nouveau et je suis en 4eme
J'adore les maths et j'aime bien les casses-têtes, mon prof de math m'avais donner un exercice comme celuila pour découvrir jusqu'à 17 marches et effectivement j'ai reussi a trouver pour 17 marches: 2584 en procédant comme Antonio0034, puis pour trouver 20 il faut:

[...]
16 marches:1597
17 marches:2584 1597+2584=4181
18 marches:4181 2584+4181=6765
19 marches:6765 4181+6765=10946
20 marches:10946

Mais bon facil de faire sa après que plusieurs aient donner la réponse...
En tout cas..

kuqib · #13

en 4eme ?
bon ben je suppose qu'avec un peu de bonne volonté j'aurais trouvé aussi, mais quand même ...
mon prof n'a jamais fait ça

marie--math · #14

J'ai un petit probléme : je suis en classe de 3iéme et j'ai un probléme de méme type : moi je doit trouver pour 15 et pour 1665 marche mais je suis un peut perdu ... Ese ce que quel qu'un pourais m'aider svp ... car j'ai peut étre trouvez le résulta pour 15 qui est 987 mais je ne connait pas le calcul ...

dhrm77 · #15

Si tu as lu plus haut, tu sais deja qu'il s'agit de la suite de Fibonacci. Donc il te suffit de faire des recherches pour trouver le 17eme et 1667eme elements de la suite... Et lire les articles inombrables sur le sujet t'apprendra comment calculer cette suite.

SFGSG · #16

Merci tout le monde!!

kosmogol · #17

à la prochaine

clementmarmet · #18

c'était quoi ça?!?!?!

kosmogol · #19

un "Visiteur"

MthS-MlndN · #20

jano · #21

ils y a 3 façon

MthS-MlndN · #22

Non, bien plus ! Relis nos réponses ci-dessus, et notamment le lien entre ce problème et la suite de Fibonacci

MissClara015 · #23

OUI !!! C'est ça !!! Merci !!!
J'ai quand même trouvé quelque chose : si on fait le resultat de 1 marche + le résultat de 2 marches, on trouve le résultat de 3 marches.
1 m : 1 solution
2 m : 2 solutions
3 m : 3 solutions
4 m : 5 solutions
5 m : 8 solutions.....

Mais ma question c'est : pour trouver 1001 marches, on fait comment ???

gwen27 · #24

On va sur dcode...

Le résultat de F(1002) vaut

11379692539836027225752378255222 41755727459303537305131450866341 76691092536145985470146129334641 86690278367304232208862586339605 28886900969695771736963705621804 00527049497109023054114771394568 040040412172632376

Ce nombre a 210 chiffre(s)

Nicouj · #25

Il suffit d'adapter dans le langage de programmation que l'on préfère

f(x) = si x inférieur ou égal à 1 alors 1 sinon retourner f(x-1) + (f(x-2)

et puis lancer f(1002) XD

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 21-06-2009 22:00:47

dénombrement : grenouille et escaliee

#0 Pub

#2 - 21-06-2009 22:06:38

Dénnombrement : grenouille et escalier

#3 - 21-06-2009 22:12:32

Dénombrement : greouille et escalier

#4 - 21-06-2009 22:46:17

Dénombrement : grenouille et escalie

#5 - 22-06-2009 12:50:59

dénombrement : geenouille et escalier

#6 - 22-06-2009 19:17:38

Dénombrement : grenouille et esclaier

#7 - 22-06-2009 20:20:29

dénombrement : greniuille et escalier

#8 - 23-06-2009 18:43:14

Dénoombrement : grenouille et escalier

#9 - 23-06-2009 23:58:23

Dénombrement : grenouille et escalieer

#10 - 24-06-2009 16:46:37

énombrement : grenouille et escalier

#11 - 24-06-2009 20:28:20

dénombrement : greniuille et escalier

#12 - 11-06-2010 20:30:05

DDénombrement : grenouille et escalier

#13 - 12-06-2010 18:22:23

dénombrement : grenouille et esczlier

#14 - 23-10-2010 12:54:24

dénombrement : grenouille et zscalier

#15 - 23-10-2010 17:58:43

dénombrement : grenouillr et escalier

#16 - 11-05-2011 16:10:01

Dénombrement : grenouille et escaliier

#17 - 11-05-2011 17:04:53

Dnombrement : grenouille et escalier

#18 - 11-05-2011 17:52:39

Dénombrement : grenouille et escallier

#19 - 11-05-2011 18:07:03

dénombrzment : grenouille et escalier

#20 - 12-05-2011 11:35:14

dénombrement : grenouille zt escalier

#21 - 28-10-2011 15:01:58

dénombrement : grenouille et escaloer

#22 - 28-10-2011 16:01:15

Dénomrbement : grenouille et escalier

#23 - 31-10-2011 12:43:47

Dénombrement : grenouille e tescalier

#24 - 31-10-2011 13:32:10

dénombrement : grenouille et escaluer

#25 - 31-10-2011 15:14:20

Dénombremetn : grenouille et escalier

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums