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
[+]

 #76 - 20-11-2013 00:35:44

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

Promenon-snous dans le train

Merci à fix33 de défendre ma très simple démonstration. Au début je me suis lancé
(et rapidement perdu) dans un "arbre" énumérant tous les chemins possibles quand
j'ai compris que je pouvais m'en affranchir ainsi. Par contre, j'ai un petit soucis avec
la "théorie oscillatoire" sur laquelle je reviendrai dans la semaine.

#0 Pub

 #77 - 20-11-2013 09:21:47

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

Promenons-nous danss le train

Pour [latex]n=100[/latex] on obtient instantanément (en programmant)       
[TeX]m=9801=(n-1)^2[/latex]  minutes.

Détaillons le cas [latex]n=8[/latex] à titre d'exemple.

                  [latex]A=
\begin{pmatrix}
0&\frac{1}{2}&0&0&0&0&0&0\cr
1&0&\frac{1}{2}&0&0&0&0&0\cr
0&\frac{1}{2}&0&\frac{1}{2}&0&0&0&0\cr
0&0&\frac{1}{2}&0&\frac{1}{2}&0&0&0\cr
0&0&0&\frac{1}{2}&0&\frac{1}{2}&0&0\cr
0&0&0&0&\frac{1}{2}&0&\frac{1}{2}&0\cr
0&0&0&0&0&\frac{1}{2}&0&0\cr
0&0&0&0&0&0&\frac{1}{2}&0\cr
\end{pmatrix}[/TeX]
[TeX]I_8-A=
\begin{pmatrix}
1&-\frac{1}{2}&0&0&0&0&0&0\cr
-1&1&-\frac{1}{2}&0&0&0&0&0\cr
0&-\frac{1}{2}&1&-\frac{1}{2}&0&0&0&0\cr
0&0&-\frac{1}{2}&1&-\frac{1}{2}&0&0&0\cr
0&0&0&-\frac{1}{2}&1&-\frac{1}{2}&0&0\cr
0&0&0&0&-\frac{1}{2}&1&-\frac{1}{2}&0\cr
0&0&0&0&0&-\frac{1}{2}&1&0\cr
0&0&0&0&0&0&-\frac{1}{2}&1\cr
\end{pmatrix}[/TeX]
[TeX](I_8-A)^2=
\begin{pmatrix}
  \frac{3}{2}&-1&\frac{1}{4}&0&0&0&0&0\cr
-2&\frac{7}{4}&-1&\frac{1}{4}&0&0&0&0\cr
\frac{1}{2}&-1&\frac{3}{2}&-1&\frac{1}{4}&0&0&0\cr
0&\frac{1}{4}&-1&\frac{3}{2}&-1&\frac{1}{4}&0&0\cr
0&0&\frac{1}{4}&-1&\frac{3}{2}&-1&\frac{1}{4}&0\cr
0&0&0&\frac{1}{4}&-1&\frac{3}{2}&-1&0\cr
0&0&0&0&\frac{1}{4}&-1&\frac{5}{4}&0\cr
0&0&0&0&0&\frac{1}{4}&-1&1\cr
\end{pmatrix}[/TeX][TeX](I_8-A)^{-2}=
\begin{pmatrix}
231&224&205&176&139&96&49&0\cr
448&436&400&344&272&188&96&0\cr
410&400&370&320&254&176&90&0\cr
352&344&320&280&224&156&80&0\cr
278&272&254&224&182&128&66&0\cr
192&188&176&156&128&92&48&0\cr
98&96&90&80&66&48&26&0\cr
50&49&46&41&34&25&14&1\cr
\end{pmatrix}[/TeX]
Par suite pour [latex]n=8[/latex] on a

                     [latex]m=(I_8-A)^{-2}[8,2]=49=(n-1)^2[/latex]  minutes

 #78 - 20-11-2013 11:05:58

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

Promenons-nous dan sle train

> Franky1103 #30
> J’appelle t(i) le temps mis en moyenne pour atteindre le wagon numéro i.
> On a trivialement: t(1) = 0 et t(2) = 1.

Il me semble que ça ne va pas...
t(1) ne semble pas le temps mis en moyenne pour atteindre le wagon numéro 1.
Il semble que t(1) soit le temps minimum pour atteindre le wagon numéro 1.
De même pour t(2).

 #79 - 20-11-2013 11:33:55

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

prpmenons-nous dans le train

Le parcours du voyageur commence dans le wagon n°1: on a t0 = t(1) = 0. Puis il n'a pas d'autre choix que d'aller dans le wagon n°2, puisqu'il n'y a pas de wagon n°0: on a t(2) = 1 qui est la durée exacte (même pas moyenne). Après pour aller dans le wagon n°3, ça se complique ...

 #80 - 20-11-2013 12:24:19

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

promenonq-nous dans le train

Si j'ai bien compris, dans la preuve de Franky1103, t(n) est, lorsqu'il y a exactement n wagons, le temps moyen mis pour que le voyageur parti du wagon 1 arrive au wagon n (arrivé au wagon n, le voyageur s'assoit).

Je ne comprends pas la preuve de Franky1103 #30...

 #81 - 20-11-2013 13:37:16

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

PPromenons-nous dans le train

Moi, c'est la seule que je comprenne ! lol


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

 #82 - 20-11-2013 14:21:45

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2956

Promenonsnous dans le train

Je suis bien d'accord avec Francky pour dire que pour t(3) c'est pas évident du tout....

 #83 - 20-11-2013 15:24:48

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

Promenons-nous dans lee train

@masab
Il peut y avoir un nombre de wagons supérieur à n et t(n) est alors le temps moyen mis pour que le voyageur parti du wagon 1 arrive au wagon n pour la première fois. Après, si le voyageur n’a pas envie de s’asseoir, la SNCF dégage toute responsabilité sur la suite de son parcours. big_smile
Je ne comprends pas vraiment ce qui te chiffonne, mais tu as probablement de bonnes raisons de douter.

@nodgim
Au début, en tâtonnant, j’avais calculé t(3) comme une succession de temps imbriqués les uns dans les autres, comme suit:
t(3) = 1 + 0,5 + 0,5.(2 + 0,5 + 0,5.(2 + 0,5 + 0,5.(2 + 0,5 + 0,5.(2 + 0,5 + 0,5…. ))))
=> t(3) + 1 = 2,5 + 0,5.(2,5 + 0,5.(2,5 + 0,5.(2,5 + 0,5.(2,5 + 0,5.… ))))
=> t(3) + 1 = 2,5 + 0,5.(t(3) + 1) => t(3) = 4
A partir de t(4), ça devient vraiment coton et j’ai essayé de généraliser.

 #84 - 20-11-2013 16:02:52

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

promenons-npus dans le train

Avec la dernière précision de Franky1103 sur la définition de t(n) [en fait elle est équivalent à celle que j'ai donnée dans le message #80], j'ai finalement compris la preuve donnée par Franky.
Le point délicat est de se convaincre qu'il faut bien ajouter (t(n+1)-t(n-1))/2.
Il faut se convaincre que t(n+1)-t(n-1) est bien le temps moyen pour aller du wagon n-1 au wagon n+1. Après un peu de réflexion, on est finalement convaincu...

 #85 - 22-11-2013 00:34:10

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

promenons-nois dans le train

Nous avons vu que pour atteindre le wagon n°k la promenade moyenne dure [latex](k-1)^2[/latex] minutes.

Mais que se passe-t-il si l'on change légèrement la probabilité de monter dans le wagon

supérieur en la faisant passer, par exemple, de [latex]\frac12[/latex] à [latex]\frac13[/latex] ?

 #86 - 22-11-2013 10:07:48

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 401

promenons-bous dans le train

@titoufred #85
Si la probabilité de passer dans le wagon supérieur est 2/3, une simulation sur 100000 tirages montre que le temps moyen est de 53 minutes. Pour 1/3, la simulation est en cours, mais les premiers résultats s'échelonnent entre 900 et 1800 jours.

Ajouté :
Pour une simulation de 7000 tirages, avec p=1/3, j'obtiens un temps moyen de  2113096 minutes, soit environ 1467 jours. Les temps de parcours s'échelonnent entre 115 et 22472717 minutes. Cette dernière valeur correspond à plus de 42 ans.

Précision
Pour p=1/3, le temps moyen calculé avec la formule itérative en #90 est de 2097091 minutes, soit 1456 jours 7 heures et 31 minutes (presque 4 ans). Il ne faut pas être pressé…
Je m'aperçois que Franky1103 a déjà calculé cette valeur en #92.

 #87 - 22-11-2013 16:06:41

charly27
Passionné de Prise2Tete
Enigmes résolues : 49
Messages : 66

Promenons-nou dans le train

si il doit passer dans le train autant de temps que je passe sur l’énigme 25c, je rejoindrais l'esprit de Fernand Raynaud en disant ""un certain temps""hmm

 #88 - 22-11-2013 18:37:37

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2956

Promenons-nous danns le train

Franky1103 a écrit:

Je tente une démonstration plus rigoureuse, en laissant tomber cette histoire de
mouvement brownien, revu par Einstein, juste mais lourd à digérer.
J’appelle t(i) le temps mis en moyenne pour atteindre le wagon numéro i.
On a trivialement: t(1) = 0 et t(2) = 1. Calculons maintenant t(n+1), en fonction
des termes précédents.
Je suis dans le n-ième wagon; pour passer dans le wagon suivant (ou précédent),
je mettrai une durée de 1, multipliée par la probabilité de 0,5; il me reste à ajouter
la durée pour passer du wagon précédent au suivant qui est de: t(n+1) - t(n-1), à
multiplier par 0,5 (comme je suis remonté de 1, il faut redescendre de 2).
J’ai donc: t(n+1) = t(n) + 0,5.1 + 0,5.1 + 0,5.[t(n+1) - t(n-1)],
ce qui donne: t(n+1) = 2 + 2.t(n) - t(n-1)
Cette suite introduite dans un tableau Excel donne la solution: t(n)=(n-1)², et on
vérifie en effet aisément que: 2 + 2.(n-1)² - (n-2)² = n²
Donc: t(20) = 19² = 361 mn = 6 h 01 mn. Et voilà.

Pour ce que je comprends, c'est ce message qui semble emporter les suffrages, et en effet, cette récurrence parait parfaite.
Cependant, je ferai encore une réserve, sans doute pourra t elle être levée rapidement, j'espère en tout cas.
Quand on passe de t(n) au t(n-1) on laisse en plan le fait que pour le calcul de t(n-1), on n'a pas pris en compte les mouvements dégressifs. En effet, le temps moyen pour accéder à un wagon est tjs compté à partir du wagon précédent depuis l'origine, jamais à partir d'un wagon à reculons. Donc utiliser t(n-1) à partir de t(n) me semble peut être un peu abusif. Qui se lance pour lever ce doute ?

 #89 - 22-11-2013 19:20:22

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,474E+3

Promenosn-nous dans le train

Cela revient par symétrie à passer de t(x) à t(x+1) à l'extrémité opposée du trin et comme le calcul est le même, je ne vois pas où est le problème.

 #90 - 22-11-2013 19:20:31

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 401

Promenons-nou sdans le train

Le raisonnement de Franky1103 en #30 peut se généraliser à une probabilité p de passer dans le wagon suivant. On obtient :
t(n+1) = ( 1 + t(n) - (1-p)t(n-1) ) / p

 #91 - 22-11-2013 20:52:22

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

Promenons-nous dans el train

@enigmatus : merci pour les estimations !

nodgim a écrit:

Quand on passe de t(n) au t(n-1) on laisse en plan le fait que pour le calcul de t(n-1), on n'a pas pris en compte les mouvements dégressifs. En effet, le temps moyen pour accéder à un wagon est tjs compté à partir du wagon précédent depuis l'origine, jamais à partir d'un wagon à reculons. Donc utiliser t(n-1) à partir de t(n) me semble peut être un peu abusif. Qui se lance pour lever ce doute ?

Peu importe comment on a atteint le wagon n-1 une fois qu'on y est.

Pour [latex]i\leq j[/latex], on note [latex]t_{i,j}[/latex] le temps moyen pour atteindre le wagon j pour la première fois en partant du wagon i. Et peu importe comment on a fait pour se retrouver au wagon i, qu'on l'ait déjà dépassé ou pas... Tu vois bien que ce qui importe ce n'est pas le passé mais l'avenir. C'est beau cette phrase.

On voit alors que
[TeX]t_{i,j}+t_{j,k}=t_{i,k}[/latex] pour tous [latex]i\leq j \leq k[/TeX]
Ce qui donne en particulier [latex]t_{1,n-1}+t_{n-1,n+1}=t_{1,n+1}[/latex]

et donc [latex]t_{n-1,n+1}=t_{1,n+1}-t_{1,n-1}=t(n+1)-t(n-1)[/latex]

Voilà, la formule utilisée par Franky n'a rien d'abusif.

 #92 - 23-11-2013 00:45:23

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

Promennons-nous dans le train

Soit p la probabilité de monter dans le wagon suivant et donc 1-p celle de reculer.
t(n+1) = t(n) + p + (1-p).[1 + t(n+1) - t(n-1)]
=> t(n+1) = 1/ p + [t(n) – t(n-1)] / p + t(n-1)
Je n'arrive pas à trouver la formule générale de cette suite sad
D'ailleurs, quelqu'un aurait-il une idée ?
Mais je n'abandonne pas pour autant smile

Je calcule d'abord les premiers termes:
t(1) = 0
t(2) = 1
t(3) = 2/p
t(4) = 1 + 2/p^2
t(5) = 4/p – 2/p^2 + 2/p^3
t(6) = 1 + 6/p^2 - 4/p^3 + 2/p^4
Puis je généralise: t(n+2) = Som[a(n+2;j)/(p^j)]   (pour n-2 > j >= 0)
avec les coefficients du tableau Excel joint.

Je trouve finalement:
p=1/3 => t(20)=env. 4 ans
p=1/2 => t(20)=6 h 01 mn (résultat déjà connu)
p=2/3 => t(20)=53 mn


 #93 - 23-11-2013 11:53:43

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

Promenons-nous dans le rain

Ma méthode matricielle se généralise aussi avec la probabilité [latex]p[/latex] d'aller au wagon suivant et [latex]1-p[/latex] d'aller au wagon précédent.
On obtient aisément comme moyenne en minutes des temps mis pour atteindre le wagon 20
[TeX]\mathrm{Moyenne}(p) = (p^{18} + 90 p^{16} - 480 p^{15} + 1920 p^{14} - 5712 p^{13}[/TeX]
[TeX]+ 13188 p^{12} - 24144 p^{11} + 35544 p^{10} - 42400 p^{9} + 41092 p^8[/TeX]
[TeX]- 32288 p^7 + 20424 p^6 - 10264 p^5 + 4010 p^4 - 1176 p^3[/TeX]
[TeX]+ 244 p^2 - 32 p + 2)/p^{18}[/TeX]
D'où
[TeX]\mathrm{Moyenne}(1) = 19[/TeX]
[TeX]\mathrm{Moyenne}(1/2) = 361[/TeX]
[TeX]\mathrm{Moyenne}(2/3) = 6946817/131072 = 53.00000762939453125000000000[/TeX]
[TeX]\mathrm{Moyenne}(1/3) = 2097091[/TeX]
Voilà !

 #94 - 23-11-2013 12:14:58

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

Prmenons-nous dans le train

@masab
Je crois bien que j'ai réinventé ta méthode matricielle sous une autre forme. Sorry pour ce plagiat bien involontaire. Heureusement, on trouve exactement le même résultat.

 #95 - 23-11-2013 12:22:43

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

Proenons-nous dans le train

Reste plus qu'à trouver la formule pour k quelconque. Commencez peut-être avec [latex]p=\frac13[/latex] avant d'attaquer le cas p quelconque.

 #96 - 23-11-2013 13:39:42

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

Pormenons-nous dans le train

P = 1/3 => t(n+1) = 3 + 3.t(n) – 2.t(n-1)
Cette relation permet d’avoir les 12 premières valeurs de t(n) qui sont:
0; 1; 6; 19; 48; 109; 234; 487; 996; 2017; 4062 et 8155.
Comme 19; 109; 487 et 2017 sont premiers, la formule générale de t(n) ne peut
pas être un produit comme pour les nombres triangulaires ou tétraédriques.
J'ai également essayé de généraliser avec un polynôme de degré 9, sans succès.
Donc "drapeau blanc" pour moi.

 #97 - 23-11-2013 13:50:03

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

promenons-nous danq le train

Étant données les premières valeurs de la suite, on a envie de dire qu'en gros ça double pour passer d'un terme au suivant...

 #98 - 23-11-2013 15:01:24

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

promenpns-nous dans le train

J’ai simplifié un peu la relation:
t(n+1) = 3 + 3.t(n) – 2.t(n-1) => t(n+1) – 2.t(n) = 3 + t(n) – 2.t(n-1)
=> u(n+1) = u(n) + 3, en posant: u(n) = t(n) – 2.t(n-1), avec u(2) = 1
d’où: u(n) = 3n – 5, et ma relation simplifiée:
t(n) = 2.t(n-1) + 3n – 5
Mais je n’ai toujours pas le terme général de cette suite …

 #99 - 23-11-2013 15:16:59

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

Promenons-nous dans e train

Bien joué Franky.

Pour résoudre ce genre d'équations, une bonne méthode consiste à résoudre d'abord l'équation homogène [latex]t(n)=2t(n-1)[/latex].
On ne s'occupe pas de la condition initiale pour l'instant.
Puis tu cherches une solution particulière de l'équation avec second membre sous la forme d'un truc qui ressemble au second membre en général (ici un polynôme de degré 1). Les solutions de l'équation avec second membre sont les solutions de l'équation homogène auxquelles tu ajoutes la solution particulière. Finalement la condition initiale te permet de trouver la solution qui correspond au problème.

 #100 - 23-11-2013 16:24:13

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

promenons-nous dans ke train

t(n) = k.2^n + an + b
t(n-1) = k.2^(n-1) + a(n-1) + b
t(n) – 2.t(n-1) = -a.n + 2a – b
d’où: a = -1/3, et b= 2a + 5 = 13/3
donc: t(n) = k.2^n + (13 – n)/3
t(1) = 0 = 2k + 4 => k = -2
t(2) = 1 = 4k + 11/3 => k <> -2
Oups ! Ca ne marche pas !
Où est mon erreur ?

Edit: Ben oui ... quelle bête erreur !
a = -3 et b = -1
d’où: t(n) = k.2^n - 3n - 1
t(1) = 0 = 2k + 4 => k = 2
donc: t(n) = 2^(n+1) - 3n - 1
et je trouve comme masab.

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 : Pim, Pam 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