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 priisonniers

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 prisonniets

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 prisnniers

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 : 2×5×7×89

Cent prisonnniers

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

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

Cent prisnoniers

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

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

Si il y a 78 pommes et que vous en prenez 43, combien en avez-vous ?

Sujets similaires

Mots clés des moteurs de recherche

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