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 - 09-07-2009 15:31:42

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

cent prisinniers

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 ?



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 10-07-2009 12:45:46

kosmogol
Banni
Enigmes résolues : 49
Messages : 11,928E+3

Cent prisonnniers

Déjà vu ici, mais excellent principe, qui m'avait complètement bluffé !
Je revois ce problème avec plaisir yikes


http://enigmusique.blogspot.com/

 #3 - 10-07-2009 12:49:42

Taupine
Sage de Prise2Tete
Enigmes résolues : 49
Messages : 1073

Cnet prisonniers

Celle là je la connais déjà. Mon copain a essayé de m'expliquer, mais la solution optimale dépasse le niveau de mes connaissances mathématiques.

 #4 - 10-07-2009 14:41:34

EfCeBa
Administrateur
Enigmes résolues : ∞+1
Messages : 22×32×173

cent prisonnizrs

Le principe a été été démontré ici : http://www.prise2tete.fr/forum/viewtopic.php?id=2802

 #5 - 13-07-2009 15:34:51

papiauche
Sa Sainteté
Enigmes résolues : 49
Messages : 2125

vent prisonniers

J'ai lu la réponse sur le Web, l'énigme est vraiment difficile mais la réponse passionnante, je la retranscris au mieux.

1°) Une idée sur l'ordre des numéros dans les tiroirs.

A chaque tiroir -qu'on numérote-, on associe un numéro.
On forme ainsi 100 couples.

Pour un couple {a,b} on cherche le couple suivant sous la forme {b,c} et ainsi de suite.

On atterrit forcément à un moment sur le couple {n,a}.

On a ainsi défini un cycle.

2°) La stratégie:

chaque joueur démarre par le tiroir portant son numéro et poursuit le cycle jusqu'à trouver son numéro.

Il gagne si le cycle est de longueur inférieure à 50 et perd sinon.

3°) La situation gagnante

Il n'y a aucun cycle de longueur strictement supérieure à 50.

4°) Le dénombrement

Le nombre de cycles de longueur k dans un ensemble à 2N éléments est donné par :
[TeX]{A}_{100}^k \times \dfrac{1}{k} \times (100-k)! = \dfrac{(100)!}{k}[/TeX]
Le nombre de cycle supérieurs à 50:
[TeX]\sum_{k=51}^{100} \dfrac{1}{k}[/TeX]
qui tend pour n grand vers:
[TeX]1- log{2}[/TeX]
5°) La réponse

La probabilité de survie est l'ordre de [latex]log{2}[/latex] soit [latex]30,1%[/latex]


"Je ne lis jamais un livre dont je dois faire la critique. On se laisse tellement influencer." O. Wilde

 #6 - 14-07-2009 04:29:21

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 2991
Lieu: Fanning Island-?-Lac Tele,Mali

Cent prisoniers

Comme l'indique le livre que l'on peut lire
ici, la solution qui donne les meilleures chances est:
- d'ouvrir le tiroir qui porte son numéro, et s'il ne contient pas son numero,
- d'ouvrir le tiroir dont le numéro était dans le tiroir précédent. et ainsi de suite.
Cependant, ca ne marche que si le nombre de permutation circulaires ( la serie de nombres qui nous amene de tiroir en tiroir ) est au plus de 50 tiroirs. C'est generalement vrai s'il y a au moins 3 séries de nombres circulaires. Les chances de succes sont d'environ 30%.


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #7 - 15-07-2009 10:30:21

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

cent priqonniers

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 :
[TeX]C_{100}^k\times(k-1)!\times(100-k)! =
\frac{100!}{k!(100-k)!}\times(k-1)!\times(100-k)!=
\frac{100!}{k}
[/TeX]
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
[TeX]\sum_{k=51}^{100}\frac{100!}{k}[/TeX]
La probabilité de survivre est donc :
[TeX]1-\frac{\sum_{k=51}^{100}\frac{100!}{k}}{100!} =
1-\sum_{k=51}^{100}\frac{1}{k} \approx 31.1827821%
[/TeX]
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
[TeX]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)}
[/TeX]
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.

 

Réponse rapide

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

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pif, Paf et ?

Sujets similaires

Mots clés des moteurs de recherche

Mot clé (occurences)
Enigme des 100 prisonniers (24) — Probleme des 100 prisonniers (17) — Enigme prisonniers (17) — 100 prisonniers tiroirs (15) — Enigme prisonnier (13) — Enigme 100 prisonniers 100 tiroirs (13) — Enigme 100 prisonniers tiroirs (12) — Solution enigme 100 prisonniers (10) — Enigme 100 prisonniers (9) — Les 100 condamnes (9) — Enigme des prisonniers (9) — Les 100 prisonniers (8) — Enigme des 100 condamnes (8) — 100 prisonniers solution (7) — Enigme 100 tiroirs (7) — Probleme 100 prisonniers (6) — Probleme des prisonniers (6) — Enigme cent prisonniers (5) — Solution des 100 condamnes (5) — Enigmes prisonniers (5) — Enigme 100 prisonniers tiroirs solution (5) — Les 100 condamnes solution (5) — Enigmes mathematiques sur les prisonniers (4) — Enigme 100 condamnes (4) — Enigme prisonier permutation cycle (4) — Le probleme des 100 prisonniers (4) — Enigme des prisonniers solution (4) — 100 prisonniers sont condamnes a mort solution (3) — Enigme 100 prisonniers a resoudre 3 possibilites (3) — Enigme des 100 tiroirs (3) — Maths 3eme les 100 tiroirs (3) — Enigme des 100 prisonniers solution (3) — 100 mathematiciens 100 tiroirs (3) — Les 100 condamnes la solution (3) — Enigme de 100 euros (3) — Cent prisonniers enigme (3) — Probleme prisonnier (3) — Enigme 100 mathematicien (3) — 100 prisonniers 100 boites (3) — Enigmes cycle 2 (3) — Enigme prisonnier tiroir (3) — Prisonnier (3) — Enigme a tiroir (3) — Prisonniers tiroirs (2) — Enigme - des 100 prisonniers et des 100 tiroirs (2) — Les 100 prisonniers enigmes solution (2) — Enigme cent couple (2) — Les cent prisoniers (2) — Enigne prisonnier boite 100 (2) — Enigme100 prisonniers reponse (2) — 100 prisonniers 100 tiroirs (2) — Tiroirs enigme 100 prisonniers (2) — Les 100 condamnes tiroirs (2) — Enigmes des 100 prisonniers tiroirs (2) — Solution prisonnier jeux d enigme (2) — Probleme des 100 condamnes (2) — Enigme 10 prisonniers (2) — Solution enigme des 100 prisonniers (2) — 100 prisonniers sont condamnes a mort (2) — Pb les cents prisonniers (2) — Enigme 100 prisonnier et tirroir (2) — Les cent condamnes (2) — Deux prisonniers sont enfermes jeux de logique (2) — Enigme les 100 condamnes (2) — Cent prisonniers sont enfermes dans une piece. (2) — Le probleme des 50 prisonniers (2) — 100 prisonniers tiroirs numeros (2) — Enigme tiroir prisonnier (2) — Enigme 10 prisonier (2) — Probleme de math commode avec 100 tiroirs (2) — 100 prisonniers log2 (2) — Groupes cent prisonniers colmez (2) — Devinette a tiroir (2) — Les 100 prisonniers enigme (2) — Solution des 100 prisonneirs (2) — Enigme permutation (2) — Enigmes 100 tiroirs (2) — 100 prisonniers indice (2) — Egnime prisonier (2) — Enigme prisionnier tiroir (2) — L enigme des 100 prisonniers (2) — Enigme a tiroirs (2) — Les 100 condamnes enigme (2) — Enigma et permutations circulaire (2) — Enigme prisonnierq (2) — 100 tiroirs enigme (2) — Prisonniers 100 boites permutations (2) — L enigme les 100 condamnes solution (2) — Enigme des prisonnier (2) — Enigme des prisonniers et des tiroirs (2) — Enigme de 100 prisonniers (2) — Solution 100 prisonniers (2) — Enigmes a tiroirs (2) — Reponse+de+l enigme+les+100+condamnes (2) — Enigme et solution 100 prisonniers (2) — 100 prisionniers (2) — Probleme math prisonnier (2) — Enigme de prisonniers (2) — Enigme complexe les cent condamne reponse (2) — Enigme des 100 condamnes solution (2) — Solution de l enigme des 100 prisonniers et (2) — Enigme des 100 prisonniers reponse (2) — Enigme 100 prisonniers sont condamnes a mort (2) — Enigme mathematiques100 boites (2) — Prisonnier tiroirs numero (2) — Probleme des 30 euros (2) — Enigme 100 prisonniers condamnes a mort (2) — Prisonniers cycle enigme (2) — Les cent condamnes solution (2) — Solution les 100 condamnes enigme tirroir (1) — Les cents prisonniers (1) — Probleme tiroir prisonnier (1) — Nombre de permutations circulaires prisonniers boites (1) — Reponse enigme des 100 prisonniers (1) — Enigme les 100 prissoniers (1) — Resolution de problememath geole tour de cle (1) — Enigme des prisoniers (1) — Enigmes 100 condamnes (1) — Probleme cent mathematicien enfermes (1) — Enigmedes100prisonniers (1) — Enigme prisonnuer (1) — Probleme des n prisonniers (1) — Probleme boites prisonniers (1) — Enigme mathematique 100 euros (1) — Somme nombre ensemble (1) — Meilleures enigmes prisonniers (1) — 50 mathematiciens enfermes enigme (1) — Enigme 100 prisonniers 1-ln(2) (1) — Enigme des cents prisoniers (1) — La geole prisonnier math (1) — Probleme des prisonniers cycle (1) — Enigme maths prisonnier logarithme (1) — Enigme mathematique nombre (1) — Calculer l aire de la surface hachuree (1) — Enigme 100 prisonniers 50 tiroirs (1) — Enigme 100 prisonniers 100 boites (1) — Enigme piece prisonniers 100 (1) — Les 100 condamnes reponse (1) — Enigme 10 personnes enfermees dans une prison (1) — Solution devinette les 100 prisonniers (1) — Enigme des 27 prisonniers (1) — Enigmes a tiroir (1) — Enigme math prisonnier communiquer (1) — Solution enigme 5 prisonniers (1) — Solution enigme prisonnier (1) — Enigme logique cent prisonniers (1) — On enferme 100 prisonniers (1) — Solution enigme les 100 condamnes (1) — Enigme 100 mathematiciens boites mourir (1) — Enigme mathematique prisonniers (1) — Proba prisonniers maths (1) — Egnime prisonnier (1) — Enigme prisonnier portes (1) — Enigme prisonniers tiroirs (1) — Enigmes 100 executes (1) — Dix prisonniers sont enfermes dans une tour (1) — Enigme mathematique les 100 prisonniers (1) — Enigme prison 50 tirroir (1) — Trouver un prisonnier (1) — Enigme logique prisonier cents (1) — Reponse enigme des 100 prisonniers 100tiroirs (1) — Solution les 100 condamnes (1) — Enigme prisonnier boite (1) — Les+cents+prisonnier (1) — (1) — Trouver la solution probleme 100 euros (1) — Probleme du prisonnier (1) — Enigmes des prisonniers (1) — Enigme mathematique 100 boites (1) — Solution au probleme dix prisonniers mathematique (1) — Boite a enigme tiroir (1) — Reponce du probleme du condamne (1) — Les problemes de les prisonniers (1) — 100 boites probleme (1) — Enigme des cents euros (1) — L enigme des &aa prosonnier (1) — Solution devinette enigme prisonniers (1) — Enigme permuttation (1) — Prisonnier proba qu un cycle en 50 tours (1) — Enigmes 100 boites contenant chacune un numero (1) — Enigmes piece et prisonnier (1) — Probleme 100 prisonniers 100 tiroirs (1) — Prisonniers ampoule (1) — Enigme prisonniers 100 solution (1) — 100 prisonniers numerotes de 1 a 100 (1) — Enigme mathematicien 100 boites (1) — Prisonnier 10 portes enigme (1) — 50 personnes 100 tiroirs math 3eme (1) — Enigme des 100 prisoniers (1) — Solution de l enigme des 100 prisoniers (1) — Cent prisonniers (1) — Resolution de l enigme des prisonniers (1) — Enigme 40 prisonniers (1) — Solutiondevinette prisonnier (1) — Reponse enigme des 3 prisonnier (1) — Reponse enigme math 100 prisonniers (1) — Problem of 100 prisoniers (1) — Enigme prisonniers nombre (1) — Enigme des 100 prisonniers tiroirs (1) — Enigme des 100 prisonniers avec les tiroirs (1) — Cent prisonniers log(2) enigme (1) — Solution enigme la serie le prisonnier (1) — Egnime 100 prisoniers 7 (1) — Cent prisonniers sont enfermes dans une piece (1) — Enigme ouvrir tiroir (1) — Prisonniers 100 boites (1) — Prisonniers permutation (1) — Enigme des 100 prisonniers 100 tiroirs (1) — Enigme des 100 prisonniers et 100 tiroirs (1) — Enigme prisonniers bouton 1 0 (1) — 100 tiroirs prisonniers enigme (1) — Egnime 100 condamnes (1) — Devinette condamne response (1) — Enigme mathematiciens tiroirs (1) — Devinette de math cycle 1 (1) — Solution des 100 prisonniers et des 100 tiroirs (1) — Devinette les trois prisonniers (1) — Permutation probleme 100 prisonier (1) — Enigme vu dans cent (1) — Probleme de 100 prisoniers (1) — Les condamnes devinette (1) — 100 prisonniers enigme tiroir (1) — L enigme des cents prisonnier (1) — Les prisonniers et les 100 tiroirs (1) — Reponse enigme 100 euros (1) — Reponse enigme des 100 couples (1) — L&#39;enigme des 100 prisonniers reponse (1) — Math trouver le nombre de participants (1) — Enigme des 100 prisonniers 100 tiroirs solution (1) — Mathematiciens prisonnier enigme (1) — Enigme prisonnier deux portes (1) — Enigme des cent (1) — Enigme du prisonnier enferme dans une tour (1) — Solution de l enigme 100 prisonniers tiroirs (1) — Enigme des cent prisonniers solution (1) — Mathematiques probleme des 100 prisonniers boites (1) — Probleme math prisonnier permutations cycles (1) — La solution pour les 100 prisoniers (1) — Probleme cent prisonnier (1) — 100 condamnees enigme mathematique (1) — Solutions enigmes 100 prisonniers (1) — Prisonniers tiroires (1) — Prisonnier et tiroire enigme (1) — Trouver son numero 100 tiroirs (1) — Enigme jeu de role (1) — Tiroirs et prisonniers (1) — 100 prisonniers enigme (1) — Dix prisonniers enigmes (1) — Enygme des prisonniers (1) — Enigme 100 euros (1) — Prisionner 100 tiroirs (1) — Probleme mathematique 100 moins 1. 50 moins 49 (1) — Enigme 100 prisonniers tiroir (1) — Solution les 100 prisonniers (1) — Nombres circulaires (1) — Probleme du prisonnier 100 prisonnier (1) — Enigme solution les 100 prisonniers (1) — Boite tiroire enigme (1) — Enigmes des 100 condamnes reponse (1) — Tiroirs enigme numero (1) — 100 prisonniers numeros 100 boites (1) — Enigme cent condamnes (1) — Cent prisonniers tiroirs casse tete solution (1) — Devinette 50 prisonnier et une piece (1) — Solution enigme 100 euros (1) — Enigme 12 prisonniers (1) — 100 prisonniers enigme tirroirs (1) — Permutation 100 prisoniers (1) — Enigme prisonnier tirroirs (1) — Reponse enigme 100 prisonniers tiroirs (1) — L enigme des 1oo prisonniers (1) — Enigme cycle 100 (1) — Dix prisonniers sont enfermes dans une piece circulaire (1) — Enigme 100 prisonnier 30% (1) — Enigme des 100 prisonniers grec (1) — Prisonnier tiroir enigme polytechnique (1) — Enigme prisonneirs tirroirs (1) — L&#39;enigme des 100 prisonniers (1) — Enigme mathematiciens numeros boites (1) — Enigme 100 prisonniers reponse (1) — Reponse enigme les 100 condamnes (1) — Solution 100 prisonnier 100 tiroirs (1) — 100 prisionnier 50 tiroir (1) — Enigmes+des+100+prisonniers (1) — Dictateur (1) — Solution de une prison avec 100 prisonniers reponce c 99 (1) — Probleme des 100 prisonniers origine (1) — Un prisonnier enferme dans une piece (1) — Enigme+des+100+condamnes (1) — Enigme c.u.l.c.e. (1) — 100 tiroirs enigme solution (1) — Cent prisionnier (1) — Les 100 prisonniers solution (1) — Solution enigme 100 prisonniers 100 tiroirs (1) — Enigme des condamnes (1) — Tiroirs prisonniers (1) — Reponse 100 prisonniers (1) — Probleme des 100 prisonniers (1) — Probleme mathematique des 500 prisonniers (1) — Enigme 50 prisonniers (1) — Soluce 100 prisonniers (1) — Solution enigme des 100 prisonnier (1) — Engime pur cent (1) — Enigmes des 100 prisonniers (1) — Enigme 100 prisonniers tiroirs ln2 (1) — 100 prisonniers tiroires enigme (1) — Prisonnier et tiroir (1) — Problemes ouverts niveau troisieme (1) — Ecrire a un prisonnier (1) — Serie tv resolution enigmes avec prisonnier (1) — 100 boites prisoniers enigme (1) — Enigme prisonniers numeros tiroirs (1) — Resolution du probleme des prisonniers (1) — Enigme cents (1) — Enigme les 100 condamnes numero solution (1) — Problemes boites 100 mathematicien (1) — Enigme du prisonnier (1) — 100 condamnes (1) — Solution enigme les 100 condomne (1) — Solution 100 mathematiciens boites (1) — Enigme 100 portes prisonniers (1) — Probleme prosonniers (1) — Prisonnier jeton piece enigme (1) — 100 tiroirs prisonniers (1) — Enigme des boites de 1 a 100 (1) — Jeu prisonnier 1 100 (1) — 1 -ln2 enigme des 100 prisonniers (1) — Probabilite permutations cycle n/2 (1) — Solution l?enigme des 100 mathematiciens (1) — Enigme prisonnier esperance superieur (1) — Un couple enferme dans une piece enigme (1) — Reponse enigme des 50 prisoniers (1) — Enigme 100 prisoniers (1) — Trois cents tiroirs probleme (1) — L enigmes des 100 condamnes (1) — Enigme pur cent (1) — Les 100 condamnes enigme tiroir (1) — Enigme probleme des condamnes (1) — Polytechnique les prisonniers tiroirs (1) — Enigme 50 tirroir (1) — Prisonnier tiroir enigme (1) — 100 prisonniers tiroirs enigme (1) — ?nigmes avec prisonniers (1) — Mathematique enigme des prisonniers (1) — 10 prisonniers 10 tiroirs (1) — L enigne des 100? (1) — Exercice mathematique prisonnier dans une geole (1) — Enigme 100 prisonniers solution (1) —

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