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

 #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 wink

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

  • |
  • Répondre

#0 Pub

 #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 !

 #3 - 04-05-2014 14:41:34

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,426E+3

La voie du asard

En maths on appelle ça un dérangement : http://www.bibmath.net/dico/index.php?a … ncare.html

Bienvenu sur le site smile

Vasimolo

 #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 smile

 #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 wink

 #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 ! big_smile

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

 #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 yikes

 #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 wink

@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 smile


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

 

Réponse rapide

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

Répondez (numériquement) à la petite énigme suivante : 

Un berger a 40 moutons, ils meurent tous sauf 18, combien en reste-t-il ?

Sujets similaires

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