Bienvenue sur P2T !

Je propose : 1-1/(n^n).

Mais je ne suis pas trop sûr !

@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

@golgot59 : bien essayé, mais ce n'est qu'une coïncidence

@Klimrod : un raisonnement très intéressant ... et tout à fait correct ^^. Finalement j'aime beaucoup ce forum, on apprend plein de trucs xD

@Franky1103 : ton approche est tout à fait correcte, dommage qu'elle soit incomplète ... mais l'idée de base est là ^^

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

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]

@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

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