Écrire une réponse @ Prise2Tete

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

	Forum » Enigmes Mathématiques » Cent prisonniers Écrire une réponse Attention : Aucun indice ou demande d'aide concernant les énigmes de Prise2Tete n'est accepté sur le forum ! Rends-toi sur le cercle des sages si tu as besoin d'aide ! Tout nouveau message ou sujet ne respectant pas cette règle sera supprimé, merci. Rédige ton message Nom Courriel \| \| \| \| Upload \| Aide Message [quote=Nicouj]Bravo a tous. En effet la stratégie consiste donc a commencer par ouvrir le tiroir avec son propre numéro. Si le numéro dans ce tiroir n'est pas le bon alors on ouvre le tiroir correspondant au numéro que l'on vient de découvrir et ainsi de suite jusqu'a ce que l'on trouve son numéro ou que l'on ouvre 50 tiroirs. Ainsi, lorsque la répartition des nombres dans les tiroirs est une permutation qui ne contient aucun cycle strictement supérieur a cinquante les prisonnier sont sûrs de s'en sortir. Et inversément si il existe un cycle strictement supérieur a 50 alors ils sont tous sûrs de mourrir. Comme les nombres sont répartis dans les tiroirs de manière aléatoire, la probabilité finale que les prisonniers meurrent est égale "au nombre de permutation de 100 nombres avec un cycle > 50" divisé par "le nombre total de permutations de 100 nombres". Et la probabilité qu'ls s'en sortent est un moins leur proba de mourir. Le nombre total de permutation de 100 nombres est [latex]100![/latex] (cent choix pour le premier, 99 pour le second ...) Le nombre de permutions contenant 1 cycle de taille k>50 est : D'abord je choisi les nombres qui vont constituer le cycle. Je choisit k nombres parmi 100 : [latex]C_{100}^k[/latex] possibilités. Ensuite une fois ces k nombres choisis, je peux faire toutes les permutations circulaires de taille k sur ces nombres : il y en a [latex](k-1)![/latex]. En effet on les compte comme on compte toutes les permutations possibles (cent choix pour le premier, 99 pour le deuxieme ...) sauf que l'on réserve 1 pour la fin interdisant ainsi de finir le cycle avant qu'il ne soit de taille k. Enfin on peut permuter tous les nombres en dehors du cycle comme on veut : [latex](100-k)![/latex]. Finalement le nombre de permutations avec un cycle k>50 est : [latex]C_{100}^k\times(k-1)!\times(100-k)! = \frac{100!}{k!(100-k)!}\times(k-1)!\times(100-k)!= \frac{100!}{k} [/latex] Au passage notez que pour les permutations avec cycle <= 50, le calcul ne peut se faire de cette façon car on compterais plusieurs fois la meme permutations vu que l'on s'autorise toutes les possibilités dans les nombres non selectionés qui sont au moins 50. Le nombre total de permutation avec cycle >50 est donc [latex]\sum_{k=51}^{100}\frac{100!}{k}[/latex] La probabilité de survivre est donc : [latex]1-\frac{\sum_{k=51}^{100}\frac{100!}{k}}{100!} = 1-\sum_{k=51}^{100}\frac{1}{k} \approx 31.1827821% [/latex] En suivant les même étapes on peut généraliser le probleme pour un nombre [latex]2n[/latex] quelconque de prisonniers ayant le droit d'ouvrir [latex]n[/latex] boites. Leur chance de survie est alors [latex]1-\sum_{k=n+1}^{2n}\frac{1}{k} = 1-\sum_{k=1}^{2n}\frac{1}{k} + \sum_{k=1}^{n}\frac{1}{k} \approx 1-\ln{(2n)}+\ln{(n)} = 1-\ln{(2)} [/latex] Dans le cadre général les chances de gagner sont donc toujours approximativement [latex]1-\ln{(2)}\approx 30.6852%[/latex] quelque soit le nombre de participants !! C'est un résultat vraiment surprenant vu qu'à priori on a le sentiment que chaque nouveau prisonnier condanne un peu plus le groupe.[/quote] Options Ne pas convertir les émoticônes sur ce message Sécurité Répondez à la devinette suivante : Le père de toto a trois fils : Pim, Pam et ? Retour Résumé de la discussion Nicouj 09-07-2009 15:31:42 Cent prisonniers sont enfermés dans une piece. On leur a attribué un nombre entier unique entre un et cent à chacun. Tous les prisonniers ont connaissance de leur nombre et peuvent communiquer tant qu'ils sont dans cette piece. À un moment donné on va commencer à appeler un prisonnier de maniere aléatoire et l'amener dans une autre piece complètement isolée des autres prisonniers. Dans cette piece se trouve un meuble constitué de cent tiroirs numérotés de un à cent. Au fond de chaque tiroir est écrit un nombre entier unique entre un et cent. Une fois dans la pièce le prisonnier est autorisé à ouvrir jusqu'à cinquante tiroirs. Si il ouvre le tiroir où se trouve son nombre alors il est conduit dans une troisième piece évidemment isolée des deux autres. Si après avoir ouvert cinquante tiroirs il n'a pas trouvé son numéro alors les cents prisonniers sont froidement exécutés. Tous les prisonniers vont être appelés à tour de role dans cette pièce dans un ordre complètement aléatoire jusqu'à ce qu'un prisonnier échoue, ce qui signifie la mort pour tous, ou bien que tous prisonniers arrivent à trouver leur nombre et obtiennent ainsi la liberté tous ensemble. Quelles sont les meilleures chances de survies des cents prisonniers ? 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