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 $p = \frac12$. On passe d'un temps quadratique à un temps exponentiel.

Quelle peut donc être la formule pour $p = \frac23$ ?

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 $p=\frac{1}{4}$,  on obtient $t_n=\frac{3^n}{2\ }-2\,n+\frac{1}{2}$ ;

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

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 $p=1/5$, on obtient $t(n) = (2/9)*(4)^n +(-5/3)*n + (7/9)$

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

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

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

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

Bravo masab !

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

Oui bravo masab !

On voit que la valeur critique est $p=\frac12$.

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


Pour tous ceux qui voudraient savoir comment trouver la suite $(t_n)$ à partir de

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

On cherche les racines du polynôme caractéristique $p X^2 - X + q$ :

ce sont $1$ et $\frac{q}{p}$.

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

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

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

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

On pose $p=\frac{1}{2}+\varepsilon$ où $\varepsilon\not=0$ . On a
$$\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)$$
De plus
$$\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}$$
Par suite
$$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$$ $$t(n,p)=n^2-2n+1+\mathrm{o}(1)$$ $$t(n,p)=(n-1)^2+\mathrm{o}(1)$$
Or $\mathrm{o}(1)$ désigne une fonction qui tend vers $0$ quand $\varepsilon\overset{\not=}{\to} 0$.

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

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.