Inscription / Connexion Nouveau Sujet
Niveau Maths sup
Partager :

denombrement

Posté par dol (invité) 11-12-04 à 15:28

si vous pouviez m'aider pour ce petit problème , svp!

On considère un escalier de 15 marches (de mêmes hauteurs). Une grenouille se présente devant celui-ci. Pour arriver à la 15e marche, elle peut de façon aléatoire faire des bons simples (1 marche gravie) et des bonds doubles (2 marches à la fois). On désire connaître le nombre de possibilités dont dispose la grenouille pour atteindre le haut de l'escalier.

Soit X le nombre de bonds simples et Y  le nombre de bonds doubles.
1. Evaluer X+2Y. Donner les valeurs possibles de X, Y et X+Y.
2. Pour chaque valeur k de X ainsi trouvées indiquer le nombre de façons d'effectuer ces k bonds simples.
3. En déduire le nombre total de possibilités, sa valeur numérique.

Posté par
isisstruiss
re : denombrement 11-12-04 à 15:58

Qu'est-ce que t'as pas compris? Le point 1 m'a pas l'air difficille, tu l'as réussi?

Posté par dol (invité)re : denombrement 11-12-04 à 16:23

X+2Y=15
X de 1 à 15
Y de 1 à 7

pour le reste je sais pas trop

Posté par
isisstruiss
re : denombrement 11-12-04 à 16:55

Alors le 2 non plus n'est pas difficille. Je commence
X=1 => Y=7 donc une façon. Il reste juste à savoir quand le pas simple sera effectué. Au début, après le premier pas double, après le deuxième pas double, ... ou en dernier. Donc il y a 8 possibilités.
X=2 => Y=6.5 donc pas possible
etc

Posté par dol (invité)re : denombrement 11-12-04 à 17:00

pour la question 1, qu'elles sont les valeurs possibles de X+Y, pour toi?

Posté par
isisstruiss
re : denombrement 11-12-04 à 17:26

Si tu regardes déjà les valeurs possibles de X et Y ça va tout seul après. Par exemple on a vu que X=1 => Y=7 => X+Y=8

Posté par dol (invité)re : denombrement 11-12-04 à 17:37

d'accord!!

Posté par dol (invité)re : denombrement 12-12-04 à 11:31

Regarde un peu la suite du problème

Appelons Fn le nombre total de possibilités qu'à la grenouille pour atteindre la nième marche. De même Fn-1...

1. Avant de sauter pour arriver à la nième marche, où peut se trouver la grenouille? En déduire une relation entre Fn, Fn-1 et Fn-2.

2. Evaluer directement F1, F2, calculer F15.

3. Généraliser: en utilisant le triangle de Pascal, démontrer par récurrence que pour tout entier naturel:
(n   0)+(n+1   2)+(n+2   4)+….(2n   2n)=F2n
(n+1   1)+(n+2   3)+(n+3   5)+…+(2n+1   2n+1)=F2n+1


Complément :

1. Soit (Un) définie par Un=Fn/Fn-1. Calculez U1, trouver une relation de récurrence entre Un et Un-1.

2. On pose h=(1+5)/2 et on définit Vn par Vn=(Un-h)/(Un+1/h). Montrer que Vn est une suite géométrique dont précisera le premier terme et la raison. On pourra remarquer que h²=h+1 et h3=2h+1.

3. En déduire l'expression de Vn puis de Un. Montrer que Un converge et préciser sa limite. Que dire de lim Fn quand n tend vers + ?
  

Posté par dol (invité)re : denombrement 12-12-04 à 13:53

alors , vous capitulez?

Posté par dol (invité)re : denombrement 12-12-04 à 18:21

svp!

Posté par
franz
re : denombrement 12-12-04 à 18:29

Et si le F qui permet de nommer la suite désignait Fibonacci ?

Posté par
franz
re : denombrement 12-12-04 à 18:31

Où en es-tu dans ton problème ?

Posté par dol (invité)re : denombrement 12-12-04 à 18:48

J'essaie de trouver la relation entre Fn, Fn-1 et Fn-2. Apparemment ce serait Fn= Fn-1+ Fn-2. mais je n'arrive pas comprendre pourquoi?

En fait je n'ai jamais entendu parlé de Fibonacci

Posté par
franz
re : denombrement 12-12-04 à 19:07

Oui, ta relation est bonne.

Pour parvenir à la marche n, la grenouille venait
- soit de la marche n-2 et a fait un bon de 2 marches,
- soit de la marche n-1 et a fait un bon d'une marche.

donc Fn = Fn-2+Fn-1

Posté par
franz
re : denombrement 12-12-04 à 19:15

F_1=1
F_2=1
...
F_{15}=610

Posté par dol (invité)re : denombrement 12-12-04 à 19:18

oui mais pourquoi les possibiltés pour aller à la marche n-2 + celles pour aller à la marche n-1 donnent celles de n. Je comprends pas.

Admettons, mais comment tu calcules F15?

C'est un calcul de 20 lignes!!

Posté par dol (invité)re : denombrement 12-12-04 à 19:19

Je viens de voir ton message F2=2 (2 bonds simples ou 1 double). comment arrives-tu à 610?

Posté par
isisstruiss
re : denombrement 12-12-04 à 19:45

Le plus simple est de faire la somme directement. Il suffit d'additionner les deux derniers termes de la suite. Franz avait commencé, je fais encore 2 étapes:
F3=F2+F1=1+1=2
F4=2+1=3
etc jusqu'à arriver à 15. Il existe une formule directe, mais quand tu l'auras vue tu préféreras encore faire 15 sommes.

Isis

Posté par
isisstruiss
re : denombrement 12-12-04 à 19:50

Pour répondre à ta question du post précédant, c'est-à-dire pourquoi les possibilités d'aller à la marche n est la somme de celles des deux marches précédentes, il faut utiliser l'indication de la donnée: "Avant de sauter pour arriver à la nème marche, où peut se trouver la grenouille?" Le dernier saut a été de 1 marche ou de 2 marches. Donc la grenouille était soit à la marche n-1 soit à la n-2.

Posté par
franz
re : denombrement 12-12-04 à 21:15

Je suis désolé dol,

tu as tout à fait raison, \Huge F_2 = 2 \;\; !!!!

ce qui donne après 15 lignes de calcul

{F_{1}=1\\ F_{2}= 2\\ F_{3}= 3\\ F_{4}= 5\\ F_{5}= 8\\ F_{6}= 13\\ F_{7}= 21\\ F_{8}= 34\\ F_{9}= 55\\ F_{10}= 89\\ F_{11}= 144\\ F_{12}= 233\\ F_{13}= 377\\ F_{14}= 610\\ F_{15}= 987}

Posté par dol (invité)re : denombrement 12-12-04 à 21:33

je n'ai pas compris la recurrence si tu peux m'aider...

Posté par
franz
re : denombrement 12-12-04 à 22:03

Hypothèse de récurrence :
(Hn) : \begin{tabular}{lcl} F_{2n} & = & \bigsum_{i=0}^n \( {\array{n+i\\2i} } \)\\ F_{2n+1} & = & \bigsum_{i=0}^{n} \( {\array{n+1+i\\2i+1} } \)\end{tabular}

Initialisation : (H1)
\begin{tabular}{c} \bigsum_{i=0}^1 \( {\array{1+i\\2i} } \) = \( {\array{1\\0} } \)+ \( {\array{2\\2} } \) = 1+1 =2 = F_{2} \\ \bigsum_{i=0}^{1} \( {\array{n+1+i\\2i+1} } \) = \( {\array{2\\1} } \)+ \( {\array{3\\3} } \) = 2+1 = 3 = F_{3} \end{tabular}

Hérédité :
Supposons (Hn-1) vraie
\begin{tabular}{ccl} F_{2n} & = & F_{2n-1}+F_{2n-2}\\ \vspace{5} \\ & = & \bigsum_{i=0}^{n-1} \( {\array{n-1+i\\2i} } \) +\bigsum_{i=0}^{n-1} \( {\array{n-1+1+i\\2i+1} } \) \\ \vspace{5} \\ & = & \( {\array{n-1\\0} } \) + \bigsum_{i=1}^{n-1} \( {\array{n-1+i\\2i} } \) + \bigsum_{i=0}^{n-2} \( {\array{n+i\\2i+1} } \) + \( {\array{2n-1\\2n-1} } \) \\ \vspace{5} \\ & = & 1 + \bigsum_{k=n}^{2n-2} \( {\array{k\\2(k+1-n)} } \) + \bigsum_{k=n}^{2n-2} \( {\array{k\\2(k-n)+1} } \) + 1 \\ \vspace{5} \\ & = & 1+\bigsum_{k=n}^{2n-2} \( {\array{k+1\\2k-2n+2} } \)+1 \\ \vspace{5} \\ & = & \( {\array{2n\\0} } \) + \bigsum_{j=1}^{n-1} \( {\array{n+j\\2j} } \) + \( {\array{2n\\2n} }\) \hspace{200} (j=k+1-n) \\ \vspace{5} \\ & = & \bigsum_{j=0}^{n} \( {\array{n+j\\2j} } \)\end{tabular}

Je t'envoie la fin de l'hérédité plus tard

Posté par
franz
re : denombrement 12-12-04 à 22:12

\begin{tabular}{ccl} F_{2n+1} & = & F_{2n-1}+F_{2n}\\ \vspace{5} \\ & = & \bigsum_{i=0}^{n-1} \( {\array{n-1+1+i\\2i+1} } \) + \bigsum_{i=0}^{n} \( {\array{n+i\\2i} } \) \\ \vspace{5} \\ & = & \bigsum_{i=0}^{n-1} \[ { \( {\array{n+i\\2i+1} } \) + \( {\array{n+i\\2i} } \) } \] + \( {\array{2n\\2n} } \) \\ \vspace{5} \\ & = & \bigsum_{i=0}^{n-1} \( {\array{n+1+i\\2i+1} } \) + \( {\array{2n+1\\2n+1} } \) \\ \vspace{5} \\ & = & \bigsum_{i=0}^{n} \( {\array{n+1+i\\2i+1} } \)\end{tabular}

La propriété est héréditaire

Posté par
franz
re : denombrement 12-12-04 à 22:24

En admettant que F_0 = 1, (ce qui est cohérent avec ce qui précède), U_1 = 1.

F_n=F_{n-1}+F_{n-2}
\large \frac {F_n}{F_{n-1}} = 1 + \frac {F_{n-2}}{F_{n-1}}
\large U_n=1+ \frac 1 {U_{n-1}}

Posté par
franz
re : denombrement 12-12-04 à 22:46

Un rapide calcul montre que
h^2=h+1 soit en divisant par h
h=1+\frac 1 h \hspace{50}(*)

\begin{tabular}{lcl}V_n & = & \large \frac { U_n - h } {U_n + \frac 1 h } \\ \vspace{5} \\ & = & \frac { 1+ \frac 1 U_{n-1} - h } {1+ \frac 1 U_{n-1} + \frac 1 h } \\ \vspace{5} \\ & = & \frac { \frac 1 U_{n-1} - \frac 1 h } { \frac 1 U_{n-1} + h } \hspace{150} {\rm en utilisant (*)} \\ \vspace{5} \\ & = & \frac { \frac {h - U_{n-1}} {h U_{n-1}}} { \frac {h(U_{n-1}+\frac 1 h)} {U_{n-1}} } \\ \vspace{5} \\ & = & -\frac 1 {h^2} \; \frac { U_{n-1} - h } {U_{n-1} + \frac 1 h } \\ \vspace{5} \\ & = & -\frac 1 {h^2} \; V_{n-1}\end{tabular}

Posté par
franz
re : denombrement 12-12-04 à 23:01

V_n=\( \frac {-1} {h^{2}} \)^{n-1}\;V_1

Or        V_1= \frac{U_1-h}{U_1+\frac 1 h}=\frac{1-h}{1+\frac 1 h}=\frac {-\frac 1 h} h = -\frac 1 {h^2}

Donc      V_n=\frac {(-1)^{n}} {h^{2n}}

V_n= \frac{U_n-h}{U_n+\frac 1 h}\; \Longleftrightarrow \; U_n = \frac{h+\frac {V_n}h}{1-V_n}
d'où l'expression de U_n

h>1 \; \Longrightarrow \; -\frac 1 {h^2} \in ]-1,1[ \; \Longrightarrow \; \lim_{n \rightarrow \infty}V_n = 0 \; \Longrightarrow \; \lim_{n \rightarrow \infty}U_n = h = \frac {1+\sqrt 5} 2

Posté par
franz
re : denombrement 12-12-04 à 23:11

J'oubliais la fin

F_n=F_0*\Bigprod_{k=1}^n \frac {F_k}{F_{k-1}} = \Bigprod_{k=1}^n U_k

U_k \; \relstack{\sim}{k \rightarrow \infty} \frac {1+\sqrt 5} 2  et   \( \frac{1+\sqrt 5} 2\)^k \relstack{\longrightarrow}{k \rightarrow \infty} \; \infty  donc

\Large F_n \; \relstack{\longrightarrow}{n \rightarrow \infty} \; \infty  

Ouf

Posté par dol (invité)re : denombrement 13-12-04 à 07:51

ouah!!!!!!!!!!!! merci

Posté par dol (invité)re : denombrement 13-12-04 à 08:02

en fait tu peux m'expliquer ton hypothese de recurrence

Posté par
franz
re : denombrement 13-12-04 à 20:58

L'hypothèse de récurrence comporte 2 assertions, l'une concerne les termes pairs de la suite (F), l'autre les termes impairs. Or la formulation de ces 2 assertions diffère.
Pour vérifier l'hypothèse de récurrence, il faut vérifier que l'initialisation et l'hérédité sont vraies pour les termes pairs et les termes impairs d'où la nécessité de vérifier les 2 points.

Posté par dol (invité)re : denombrement 13-12-04 à 21:13

merci beaucoup pour ton aide

Posté par
franz
re : denombrement 15-12-04 à 00:11

Je suis ravi que cela te rende service. Ca me fait plaisir d'avoir un retour sur les messages que j'ai pu envoyer et savoir qu'ils ne restent pas lettre morte.
A bientôt

Posté par dol (invité)re : denombrement 15-12-04 à 18:02

Salut! je suis en train de revoir ce que tu as fait et j'essaie de comprendre.

Comment expliques-tu: Vn=(-1/h²)n-1.V1? En fait que veut dire

Posté par
franz
re : denombrement 15-12-04 à 23:45

\Bigprod signifie produit. C'est la même chose que \Bigsum si ce n'est que l'on multiplie tous les termes au lieu de les additionner.

En ce qui concerne V_n=(-\frac 1 {h^2})^{n-1}.V_1, on vient de prouver à la ligne au dessus que la suite est géométrique (V_n=-\frac 1 {h^2}.V_{n-1}) . Pour écrire le terme de rang n en fonction du premier terme et de la raison, reporte-toi à un cours sur les suites géométriques.

Posté par dol (invité)re : denombrement 16-12-04 à 18:35

D'accord. Tu m'as beaucoup aidé, merci

A un prochain problème, peut-être!!



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1674 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !