|
#76 - 20-11-2013 00:35:44
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3220
- Lieu: Luxembourg
promenond-nous 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.
#77 - 20-11-2013 09:21:47
- masab
- Expert de Prise2Tete
- Enigmes résolues : 44
- Messages : 971
promenons-nius dans 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 : 971
Promenons-onus dans le 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 : 3220
- Lieu: Luxembourg
Proemnons-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 : 971
Promenons-nous dans le trani
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
Promenons-nous dnas le train
Moi, c'est la seule que je comprenne !
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 : 3802
promenons-nous sans 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 : 3220
- Lieu: Luxembourg
promenons-nous dans le traib
@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. 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 : 971
primenons-nous 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 : 1749
Promenons-nous dans el 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
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
Proenons-nous 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-bous 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""
#88 - 22-11-2013 18:37:37
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
promenons-noys dans 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,969E+3
Promenons-nous dnas 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
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
Promenons-nous dns 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 : 1749
Promenons-nous dans le tran
@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 : 3220
- Lieu: Luxembourg
promenons-nous dans le traon
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 D'ailleurs, quelqu'un aurait-il une idée ? Mais je n'abandonne pas pour autant
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 : 971
Promenons-nous dans le ttrain
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 : 3220
- Lieu: Luxembourg
promenons-nous dans le rrain
@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 : 1749
Promennons-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 : 3220
- Lieu: Luxembourg
Promenosn-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 : 1749
promenons-noys dans 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 : 3220
- Lieu: Luxembourg
promenons-noys 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 : 1749
Promenon-nous dans le 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 : 3220
- Lieu: Luxembourg
promenons-nous dans le trzin
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.
Mots clés des moteurs de recherche
|
|