Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #101 - 23-11-2013 16:46:18

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 682

promenons-nouq dans le train

Pour [latex]p=1/3[/latex] , on trouve [latex]t_n = 2^{n+1}-3\,n-1[/latex] .

On commence par le changement [latex]t_n=2^n\,u_n[/latex] .

#0 Pub

 #102 - 23-11-2013 19:06:35

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

promenons-nous dand le train

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] ?

 #103 - 24-11-2013 00:05:04

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2714
Lieu: Luxembourg

Promennons-nous dans le train

p = 2/3 => 2.t(n+1) = 3 + 3.t(n) – t(n-1) => 2.[t(n+1) – t(n)] = 3 + t(n) – t(n-1)
=> 2.u(n+1) = u(n) + 3, en posant: u(n) = t(n) – t(n-1), avec u(2) = 1
d’où: u(n) = k/2^n + m, et: u(n+1) = k/2^(n+1) + m
2.u(n+1) - u(n) = m = 3 => u(n) = k/2^n + 3
et: u(2) = 1 => k/4 + 3 = 1 => k = - 8 => u(n) = - 1/2^(n-3) + 3
On a donc: t(n) = t(n-1) - 1/2^(n-3) + 3
On voit que: t(n) = t(1) - s(n) + 3, avec: s(n) = Som[1/2^i], i variant de -1 à n-3
d’où: s(n) = 4 - 1/2^(n-3) => t(n) = 1/2^(n-3) + a.n + b
t(1) = 0, donne: 4 + a + b = 0, et t(2) = 1, donne: 2 + 2.a + b = 1
soit: a = 3, et: b = - 7
On a donc: t(n) = 1/2^(n-3) + 3n – 7

Récapitulation
p=1/3 => t(n) = 2^(n+1) - 3n - 1
p=1/2 => t(n) = (n-1)^2
p=2/3 => t(n) = 1/2^(n-3) + 3n – 7

Challenge
Peut-on trouver une formule générale pour p quelconque (compris entre 0 et 1) ?

 #104 - 24-11-2013 01:10:04

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

Promenons-ous dans le train

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 !

 #105 - 24-11-2013 10:39:44

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3319

promenobs-nous dans le train

Et la moyenne serait-elle là même si on part d'un wagon quelconque?


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #106 - 24-11-2013 11:41:27

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 682

Promenons-nous dans le tain

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] .

 #107 - 24-11-2013 11:44:52

SabanSuresh
Elite de Prise2Tete
Enigmes résolues : 45
Messages : 1945
Lieu: Paris

promenobs-nous dans le train

@shadock : Avec p=1/2 ; n, le nombre de wagons ; x, le numéro du wagon à laquelle le voyageur commence son périple et dt, la durée de son voyage, on a :

dt = (n-1)²-(x-1)²

Avec 20 wagons :
S'il commence à 1, il prend 361 min, ouf !
S'il commence à 5, il prend 345 min.
S'il commence à 10, il prend 280 min.
S'il commence à 15, il prend 165 min.
S'il commence à 19, il prend 37 min.

Je suis pas sûr mais je pense que le "-(x-1²)", on peut le coller à toutes les formules, non ?

Edit : j'ai précisé à qui je parlais.

 #108 - 24-11-2013 11:58:07

fix33
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1198
Lieu: Devant un clavier depuis 1748

promenons-nous danq le train

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...


Je ne vien sur se site que pour faire croir que je suis treise intélligens.

 #109 - 24-11-2013 12:15:20

SabanSuresh
Elite de Prise2Tete
Enigmes résolues : 45
Messages : 1945
Lieu: Paris

promenons-nous dans le traib

Non, il ne faut pas le même temps :

Exemples :
Si on part du wagon 1 et qu'il y a 20 wagons, on prendra (20-1)²-(1-1)² = 361 minutes, c-à-d, 6 heures et une minute.
Si on part du wagon 2 et qu'il y a 21 wagons, on prendra (21-1)²-(2-1)² = 399 minutes, c-à-d, 6 heures et 39 minutes.
Si on part du wagon 3 et qu'il y a 22 wagons, on prendra 437 minutes, c-à-d, 7 heures et 17 minutes.

Remarque : à chaque fois, cela prend 38 minutes de plus, c-à-d (20-1)*2 car :

n²-x²-[(n-1)²-(x-1)²] = n²-x²-(n²-2n+1)+(x²-2x+1) = n²-x²-n²+2n-1+x²-2x+1 = 2(n-x).

 #110 - 24-11-2013 18:00:11

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 682

promenons-nius dans le train

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]

 #111 - 24-11-2013 18:17:35

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2714
Lieu: Luxembourg

Promenons-onus dans le train

Aaargh !!! Grillé par masab. Je trouve comme lui, mais il sait écrire avec latex et c'est plus joli smile

 #112 - 24-11-2013 19:05:45

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

Promenons-nous adns le train

Bravo masab !

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

 #113 - 25-11-2013 12:05:01

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 682

Promenons-nous dan le train

Ce n'est pas une conjecture !
La preuve est aisée ; il suffit de prouver la formule par récurrence à l'aide de la relation donnée par Franky
[TeX]t_{n+1} =\frac{t_n}{p}+\left(1-\frac{1}{p}\right)\,t_{n-1} + \frac{1}{p}[/TeX]
Voilà !

 #114 - 25-11-2013 16:54:53

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

promenons-noud dans le train

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".

 #115 - 26-11-2013 12:04:39

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 682

Promenons-nos dans le train

> Les conditions initiales permettent ensuite de trouver [latex]a, b, c[/latex]

Plus précisément, sachant que [latex]t_1=0,\ t_2=1,\ t_3=\frac{2}{p}[/latex] , on trouve [latex]a,b,c[/latex] comme solutions d'un système linéaire.

 #116 - 26-11-2013 17:23:23

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 682

Promenons-nous dans le trai

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 !

 #117 - 26-11-2013 17:38:03

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2714
Lieu: Luxembourg

promenons-nous sans le train

Brillante démonstration: bravo.

 #118 - 26-11-2013 18:18:04

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

Prommenons-nous dans le train

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.

 #119 - 26-11-2013 20:43:36

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 682

Promenosn-nous dans le train

Effectivement !  La relation de récurrence permet même dire que pour tout [latex]n[/latex],  [latex]t(n,p)[/latex] est un polynôme en [latex]\frac{1}{p}[/latex] . Notons que cette propriété ne saute pas aux yeux sur la formule générale donnant [latex]t(n,p)[/latex] .

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Tim, Tam et ?

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete