|
#1 - 04-05-2014 13:18:09
- LordFlowright
- Amateur de Prise2Tete
- Enigmes résolues : 19
- Messages : 9
a voie du hasard
Bonjour à tous, j'espère que cette petite énigme saura triturer vos méninges (et vos connaissances en probabilités discrètes)
Dans la campagne, à Probaland, il y a n petits villages paisibles. Chacun d'eux possède un temple reculé où les paysans méditent, avec une unique route reliant le village et son temple. Soudain, un mauvais génie débarque et mélange les routes (Abracadabra !). Chaque village se retrouve alors de nouveau relié à un unique temple ... mais pas nécessairement le bon !
Quelle est la probabilité pour qu'aucun village ne soit relié à son temple initial ?
Indice : Spoiler : [Afficher le message] Un bon moyen d'arriver au résultat est de s'intéresser à la probabilité que le k-ième village soit bien relié à son temple, avant d'utiliser la formule de Poincaré. Mais bon ... tous les chemins mènent à Rome
Bonne chance à tous ! (et j'adore ce site xD)
PS : c'est ma première énigme, donc je précise que j'ai déjà la réponse et que je ne fais pas partie des collégiens/lycéens/étudiants qui espèrent une réponse à leur devoir maison :p
#2 - 04-05-2014 13:54:35
- SabanSuresh
- Elite de Prise2Tete
- Enigmes résolues : 45
- Messages : 1951
- Lieu: Paris
La voie du hasrad
Bienvenue sur P2T !
Je propose : 1-1/(n^n).
Mais je ne suis pas trop sûr !
#4 - 04-05-2014 14:49:24
- LordFlowright
- Amateur de Prise2Tete
- Enigmes résolues : 19
- Messages : 9
la coie du hasard
@SabanSuresh : Ce n'est pas ça, je pense que le modèle que tu as pris n'est pas le bon (ou du moins pas le même que le mien ^^'). Il n'y a que les routes qui s'échangent, rien de plus, rien de moins ... Ceci dit le résultat que j'attends n'est pas immédiat et requiert un peu de calculs ...
@Vasimolo : c'est exact, même s'il manque une (toute pitite) étape pour répondre parfaitement. ce qui est le plus intéressant en fait c'est le comportement limite assez ... contre-intuitif ^^
Merci de votre accueil chaleureux
#5 - 05-05-2014 00:09:36
- golgot59
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1494
- Lieu: Coutiches
aL voie du hasard
2 villages et 2 temples : (11;22) ou (12;21). 2 possibilités, une seule ok : 1 chance sur 2
3 villages et 3 temples : (11;22;33); (11;23;32); (12;21;33); (12;23;31); (13;22;31); (13;21;32) 2 chances sur 6 donc 1/3.
4 villages et 4 temples : 24 issues possibles. Les issues OK commençant par "12" : (12;21;34;43); (12;23;34;41); (12;24;31;43) donc 3 OK. 3 aussi pour "13" et 3 pour "14". Donc 9 issues OK Finalement 9 chance sur 24 soit 3/8.
On dirait que pour "n" il y a n/(2n+2) chances.
Reste plus qu'à essayer de le prouver...
#6 - 05-05-2014 10:50:46
- LordFlowright
- Amateur de Prise2Tete
- Enigmes résolues : 19
- Messages : 9
la voiz du hasard
@golgot59 : bien essayé, mais ce n'est qu'une coïncidence
#7 - 05-05-2014 19:43:07
- Klimrod
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 4050
- Lieu: hébesphénorotonde triangulaire
La voie d uhasard
Salut,
Enfin, un problème de math que je sais résoudre !
La probabilité d'un événement, c'est le nombre de cas favorables sur le nombre de cas possibles.
Nombre de cas possibles : C'est le nombre de permutations de n éléments. Donc [latex]!n[/latex].
Nombre de cas favorables : Appelons [latex]U_n[/latex] le nombre de cas favorables quand il y a [latex]n[/latex] villages et [latex]n[/latex] temples.
Alors il y a (n-1) façons favorables de relier le village n°1, et pour chacune de ces façons, deux cas : - si le village n°1 est relié au temple n°i et vice-versa (village n°i relié au temple n°1), il y a [latex]U_{n-2}[/latex] permutations favorables des n-2 temples restants, - sinon, il y a [latex]U_{n-1}[/latex] permutations favorables des n-1 temples restants. Donc : [latex]U_n = (n-1) * (U_{n-1} + U_{n-2} )[/latex] avec [latex]U_1 = 0[/latex], [latex]U_2 = 1[/latex] et [latex]U_3 = 2[/latex]
Pour résoudre cette équation, on peut remarquer deux choses : - si la suite [latex]U_n[/latex] est solution, alors [latex]k * U_n[/latex] est solution. - si [latex]U_n[/latex] et [latex]V_n[/latex] sont solutions, alors [latex]U_n + V_n[/latex] est également solution.
Il suffit donc de trouver deux solutions différentes [latex]U_n[/latex] et [latex]V_n[/latex] et la bonne solution sera [latex]k U_n + k' V_n[/latex] avec [latex]k[/latex] et [latex]k'[/latex] fixés par les premiers termes de la suite. Malheureusement, je n'ai trouvé qu'une seule des deux solutions, de la forme [latex]U_n = k * n![/latex]
Qu'à cela ne tienne.... . Notre suite peut également s'écrire : [TeX]U_n = n U_{n-1} + (-1)^n[/TeX] Démonstration par récurrence facile : On vérifie facilement pour [latex]U_1[/latex], [latex]U_2[/latex] et [latex]U_3[/latex]. Supposons vrai jusqu'à l'ordre [latex]n[/latex]. Alors [latex]U_{n+1} = n (U_n + U_{n-1}) = nU_n + U_n - (-1)^n = (n+1)U_n + (-1)^{(n+1)}[/latex] Cqfd.
Calcul de la probabilité : Appelons [latex]P_n[/latex] la probabilité recherchée. Alors [latex]P_n = \frac{U_n}{n!}[/latex] (nombre de cas favorables sur nombre de cas possibles) [TeX]P_n = \frac{U_n}{n!} = \frac{nU_{n-1} +(-1)^n}{n * (n-1)!} = \frac{U_{n-1}}{(n-1)!} + \frac{(-1)^n}{n!} = P_{n-1} + \frac{(-1)^n}{n!}[/TeX] Finalement, [latex]P_n = P_0 + \sum_{i=0}^n \frac{(-1)^i}{i!} = \sum_{i=0}^n \frac{(-1)^i}{i!}[/latex] [TeX]\boxed{P_n = \sum_{i=0}^n \frac{(-1)^i}{i!}}[/TeX] Calcul de la limite de la probabilité : [latex]lim(P_n) = e^{-1} = 1/e[/latex] (en vertu du fait que [latex]e^x = \sum_{i=0}^\infty \frac{x^i}{i!}[/latex] )
Et voilà : quand le nombre de villages tend vers l'infini, la probabilité tend vers 1/e.
Klim.
J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.
#8 - 05-05-2014 22:24:40
- LordFlowright
- Amateur de Prise2Tete
- Enigmes résolues : 19
- Messages : 9
La voie u hasard
@Klimrod : un raisonnement très intéressant ... et tout à fait correct ^^. Finalement j'aime beaucoup ce forum, on apprend plein de trucs xD
#9 - 05-05-2014 23:35:38
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3220
- Lieu: Luxembourg
la voie fu hasard
Si, en initialisant avec f(1)=0 et f(2)=1, je pose f(n)=(n-1).[f(n-2)+f(n-1)], alors la probabilité recherchée semble être p(n)=f(n)/n!, expression que je n'arrive pas à simplifier. Ainsi p(3)=2/6=1/3; p(4)=9/24=3/8; p(5)=44/120=11/30; p(6)=265/720=53/144 ... J'ai remarqué aussi que, lorsque n tend vers l'infini, alors p(n) tend vers 1/e. Mon approche empirique ne me convient pas vraiment, mais (pour l'instant) je n'ai pas de démonstration rigoureuse. Affaire à suivre ...
#10 - 06-05-2014 11:00:16
- LordFlowright
- Amateur de Prise2Tete
- Enigmes résolues : 19
- Messages : 9
la voir du hasard
@Franky1103 : ton approche est tout à fait correcte, dommage qu'elle soit incomplète ... mais l'idée de base est là ^^
#11 - 06-05-2014 11:26:08
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3220
- Lieu: Luxembourg
La voie du ahsard
LordFlowright a écrit:Finalement j'aime beaucoup ce forum.
Attention à ne pas devenir accro. Pour info, une étude très sérieuse a montré qu’il est plus facile d’arrêter l’héroïne que P2T.
#12 - 06-05-2014 12:58:15
- Sydre
- Professionnel de Prise2Tete
- Enigmes résolues : 15
- Messages : 245
la voie di hasard
Erratum : Le raisonnement qui suit ne répond pas à l'énigme : il correspond à une situation plus compliquée ou l'intervention du vilain génie provoque la substitution d'un nombre aléatoire de villages et de temples par d'autre villages et temples choisis aléatoirement parmi tous les villages et temples existants.
Dénombrement du nombre de configurations possibles :
Il y a [latex]n^2[/latex] façons de former un doublet village-temple avec [latex]n[/latex] villages et [latex]n[/latex] temples.
On dénombre donc [latex]\binom{n^2}{n}[/latex] configurations possibles après l'intervention du vilain génie.
Dénombrement du nombre de configurations particulières :
Lorsque [latex]k[/latex] doublets village-temple sont fixés on dénombre [latex](n-k)^2[/latex] autre doublets possibles.
On peut alors obtenir [latex]\binom{(n-k)^2}{n-k}[/latex] configurations ou [latex]k[/latex] villages sont reliés à leurs temples d'origine.
Comme il y a [latex]\binom{n}{k}[/latex] façons de fixer [latex]k[/latex] doublets parmi [latex]n[/latex], on dénombre un total de [latex]\sum_{k=1}^{n} \binom{n}{k} \cdot \binom{(n-k)^2}{n-k}[/latex] configurations ou au moins un village est relié à son temple d'origine.
On en déduit donc qu'il y a [latex]\binom{n^2}{n} - \sum_{k=1}^{n} \binom{n}{k} \cdot \binom{(n-k)^2}{n-k}[/latex] configurations ou aucun village n'est relié à son temple d'origine.
Conclusion :
La probabilité pour qu'aucun village ne soit relié à son temple d'origine est : [latex]1-\frac{\sum_{k=1}^{n} \binom{n}{k} \cdot \binom{(n-k)^2}{n-k}}{\binom{n^2}{n}}[/latex].
Bonus :
On montre que [latex]\lim\limits_{n \to +\infty} \frac{\sum_{k=1}^{n} \binom{n}{k} \cdot \binom{(n-k)^2}{n-k}}{\binom{n^2}{n}} = \exp(\exp(-2)) - 1 \approx 0.145[/latex].
Par conséquent, lorsque le nombre de village tend vers l'infini, la probabilité pour qu'aucun village ne soit relié à son temple d'origine ne tend pas vers [latex]1[/latex] i.e [latex]100 \%[/latex] comme on pourrait s'y attendre mais vers [latex]0.855[/latex] i.e [latex]85.5 \%[/latex] environ
#13 - 06-05-2014 13:36:06
- SabanSuresh
- Elite de Prise2Tete
- Enigmes résolues : 45
- Messages : 1951
- Lieu: Paris
La voie du haard
Je repropose mais je crois que c'est faux ... : 1-1/n! ? Le premier village a 1/n d'être relié au bon temple. Le deuxième 1/(n-1), le troisième 1/(n-2) ... etc. Donc c'est 1 moins le produit de tout ça ....
#14 - 06-05-2014 14:25:43
- masab
- Expert de Prise2Tete
- Enigmes résolues : 44
- Messages : 971
La voie du hasad
Après de lobarieux calculs, on obtient que la probabilité cherchée est donnée par [TeX]p_n=\sum_{k=0}^{n}(-1)^{k}\frac{1}{k!}[/TeX] On a donc [TeX]p_n\to\frac{1}{\mathrm{e}}[/TeX]
#15 - 06-05-2014 17:03:44
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3220
- Lieu: Luxembourg
La voie du hasardd
Suite de mon post On aura aussi: p(n)=f(n)/n! avec f(n)=n.f(n-1)+(-1)^n, qui est le déterminant de la matrice avec des 0 sur la diagonale et des 1 partout ailleurs, ce qui est un bon début d'explication.
#16 - 07-05-2014 10:42:12
- LordFlowright
- Amateur de Prise2Tete
- Enigmes résolues : 19
- Messages : 9
la voie du hzsard
@Sydre : les calculs sont justes ... mais l'hypothèse de départ est fausse ^^'. N'oublies pas qu'après l'intervention du génie, TOUS les villages sont reliés à un seul et unique temple.
@SabanSuresh : tu utilises la propriété d'indépendance pour des probas conditionnées entre elles ... c'est un peu comme essayer d'enfiler les deux jambes de son pantalon en même temps xD. C'est pas la bonne réponse mais tu touches du doigt
@masab : après une pas si laborieuse réflexion : oui !
@Franky1103 : Un bon début effectivement ... Et oui je suis addicte à p2t mais c'est pas grave, je risque seulement un cancer du cerveau :p
#17 - 07-05-2014 11:34:43
- fix33
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1198
- Lieu: Devant un clavier depuis 1748
La voi edu hasard
Salut ! Avec 2 villages, ça donne 1 chance sur 2. Avec 3 villages, ça donne 2 chances sur 6. Avec 4 villages, ça donne 9 chances sur 24. Avec 5 villages, ça donne 42 (si je ne me suis pas trompé) chances sur 120.
Le dénominateur est évidemment n!, mais le numérateur je ne sais pas...
OEIS me donne une suite 1, 2, 9, 42, 270, 1785... mais pas de formule toute faite
Je ne vien sur se site que pour faire croir que je suis treise intélligens.
#18 - 10-05-2014 16:32:05
- LordFlowright
- Amateur de Prise2Tete
- Enigmes résolues : 19
- Messages : 9
la boie du hasard
Je commence par féliciter vos efforts et m'excuser de pas avoir donné signe de vie sur ma propre énigme (je suis un peu tête en l'air ^^')
Pour ceux qui n'ont pas trouvé et qui voudrait une réponse à l'énigme, voici la mienne :
Bien sûr, je considère qu'il y a n routes qui sont permutées entre elles, ce qui fait n! possibilités équiprobables (puisqu'on ne sait rien du comportement du génie ...). Je passe par les évènement pour ceux qui ont des notions solides en probabilités, mais comme je ne suis pas à l'aise avec les formules sur un forum n'hésitez pas à zapper les parenthèses si elles vous échappent Tout d'abord je regarde la probabilité que le k-ième village soit relié à son temple (évènement Ek) ... qui vaut (n-1)!/n! = 1/n (jusque là je pense que j'ai perdu personne, "nombre de cas favorables sur nombre de cas possibles" blabla). Ainsi, la probabilité que les k1-ième, k2-ième, ... et kj-ième villages soit tous reliés à leur temple (évènement Ek1 inter Ek2 inter ... inter Ekj) vaut (n-j)!/n! (même scénario sauf qu'au lieu d'un seul village on en considère plusieurs) Donc, la probabilité QU'AU MOINS UN village soit correctement relié à son temple (évènement E1 union E2 union ... union En) vaut, d'après la formule de Poincaré (cf ou http://www.bibmath.net/dico/index.php?a … ncare.html merci vasimolo ^^) [latex]\sum_{k=1}^n ((-1)^{k-1} \sum_{1\le i_1<...<i_k\le n} \frac{(n-k)!}{n!}) =\sum_{k=1}^n ((-1)^{k-1} \binom{n}{k} \frac{(n-k)!}{n!})[/latex] D'où la probabilité recherchée (celle de l'évènement complémentaire) : [latex]P = 1-\sum_{k=1}^n \frac{(-1)^{k-1}}{k!}=\sum_{k=0}^n \frac{(-1)^k}{k!}[/latex] qui converge vers exp(-1) quand n tend vers l'infini.
Merci de votre attention, et on se retrouve à la prochaine énigme
Mots clés des moteurs de recherche
|
|