Oui bravo masab !

Franky, tu avais fait une bête erreur pour calculer a.

La formule ne ressemble pas du tout à celle que l'on avait trouvée pour [latex]p = \frac12[/latex]. On passe d'un temps quadratique à un temps exponentiel.

Quelle peut donc être la formule pour [latex]p = \frac23[/latex] ?

Oui bravo Franky !

On a donc un exemple où le temps de promenade augmente de façon exponentielle, un autre de façon quadratique et un autre linéaire.

Allez en avant pour le challenge !

Pour progresser j'indique que l'on a :

pour [latex]p=\frac{1}{4}[/latex],  on obtient [latex]t_n=\frac{3^n}{2\ }-2\,n+\frac{1}{2}[/latex] ;

pour [latex]p=\frac{3}{4}[/latex],  on obtient [latex]t_n=\frac{1}{\ 2\times 3^{n-2}}+2\,n-\frac{7}{2}[/latex] .

Je ne suis pas sûr que c'était la question de Shadock : compte-tenu de la spécificité du wagon n°1 (on ne peut reculer), faut-il par exemple le même temps pour aller du n°1 au n°N et pour aller du n°2 au n°N+1, pour aller du n°3 au n°N+2...?
Manifestement non, du fait même qu'il ne s'agit pas de suites linéaires...

Pour [latex]p=1/5[/latex], on obtient [latex]t(n) = (2/9)*(4)^n +(-5/3)*n + (7/9)[/latex]

Pour [latex]p=2/5[/latex], on obtient [latex]t(n) = (8)*(3/2)^n +(-5)*n + (-7)[/latex]

Pour [latex]p=3/5[/latex], on obtient [latex]t(n) = (18)*(2/3)^n +(5)*n + (-17)[/latex]

Pour [latex]p=4/5[/latex], on obtient [latex]t(n) = (32/9)*(1/4)^n +(5/3)*n + (-23/9)[/latex]

Plus généralement, pour [latex]p\not=\frac{1}{2}[/latex] le temps moyen pour arriver au wagon [latex]n[/latex] est donné par
[TeX]t(n,p)=\frac{2p^2}{(2p-1)^2}\;\left[\left(\frac{1}{p}-1\right)^n - 1\right] + \frac{n}{\ 2p-1\ } + 1[/TeX]

Bravo masab !

Est-ce une conjecture ou as-tu une démonstration ?

Oui bravo masab !

On voit que la valeur critique est [latex]p=\frac12[/latex].

Pour [latex]p<\frac12[/latex], on a asymptotiquement un temps de promenade exponentiel et pour [latex]p>\frac12[/latex], on a un temps linéaire.


Pour tous ceux qui voudraient savoir comment trouver la suite [latex](t_n)[/latex] à partir de

l'équation [latex]p t_{n+1} - t_n + qt_{n-1}=1[/latex] (où l'on a posé [latex]q=1-p[/latex]), voici la méthode :

On cherche les racines du polynôme caractéristique [latex]p X^2 - X + q[/latex] :

ce sont [latex]1[/latex] et [latex]\frac{q}{p}[/latex].

Cela implique pour [latex]p\neq \frac12[/latex] que les solutions de l'équation homogène sont de la forme
[TeX]t_n = a\left(\frac{q}{p}\right)^n + c[/TeX]
Et que l'on peut chercher une solution particulière sous la forme [latex]t_n = bn[/latex]

Par conséquent, les solutions de l'équation avec second membre sont de la forme
[TeX]t_n = a\left(\frac{q}{p}\right)^n + bn + c[/TeX]
Les conditions initiales permettent ensuite de trouver [latex]a, b, c[/latex]

C'est un cas particulier de "suite récurrente linéaire avec second membre".

Pour [latex]p\not=\frac{1}{2}[/latex] on a
[TeX]t(n,p)=\frac{2p^2}{(2p-1)^2}\;\left[\left(\frac{1}{p}-1\right)^n - 1\right] + \frac{n}{\ 2p-1\ } + 1[/TeX]
Etudions la limite de [latex]t(n,p)[/latex] quand [latex]p\overset{\not=}{\to}\frac{1}{2}[/latex].

On pose [latex]p=\frac{1}{2}+\varepsilon[/latex] où [latex]\varepsilon\not=0[/latex] . On a
[TeX]\left(\frac{1}{p}-1\right)^n =e^{n\,[\ln(1-2\varepsilon)-\ln(1+2\varepsilon)]} = e^{-4n\varepsilon+\mathrm{o}(\varepsilon^2)}=1-4n\varepsilon +8n^2\varepsilon^2+\mathrm{o}(\varepsilon^2)[/TeX]
De plus
[TeX]\frac{2p^2}{(2p-1)^2}=\frac{(1+2\varepsilon)^2}{8\varepsilon^2}=\frac{1}{8\varepsilon^2}+\frac{1}{2\varepsilon}+\frac{1}{2}[/TeX]
Par suite
[TeX]t(n,p)=\left(\frac{1}{8\varepsilon^2}+\frac{1}{2\varepsilon}+\frac{1}{2}\right)\;(-4n\varepsilon +8n^2\varepsilon^2+\mathrm{o}(\varepsilon^2))+\frac{n}{2\varepsilon}+1[/TeX][TeX]t(n,p)=n^2-2n+1+\mathrm{o}(1)[/TeX][TeX]t(n,p)=(n-1)^2+\mathrm{o}(1)[/TeX]
Or [latex]\mathrm{o}(1)[/latex] désigne une fonction qui tend vers [latex]0[/latex] quand [latex]\varepsilon\overset{\not=}{\to} 0[/latex].

Par suite
[TeX]t(n,p)\to (n-1)^2\quad\mathrm{quand}\ p\overset{\not=}{\to}\frac{1}{2}\;.[/TeX]
Par ailleurs la résolution de l'énigme originale a montré que [latex]t(n,\frac{1}{2})=(n-1)^2[/latex].

Youpi !

Ok masab, tu t'es bien fait plaiz !!

En fait il suffit de regarder la tête des équations récurrentes pour voir que c'est continu en p.