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 prisonnirrs

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

Ceent prisonniers

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

cent orisonniers

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 : 6229

Cent prisonnirs

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 : 2131

Cent pprisonniers

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 : 3002
Lieu: Fanning Island-?-Lac Tele,Mali

cent prispnniers

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

Cnet prisonniers

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 (numériquement) à la petite énigme suivante : 

Dans une course, vous doublez le 42ème, en quelle position êtes-vous ?

Sujets similaires

Mots clés des moteurs de recherche

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