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

cenr prisonniers

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 prisonnierd

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

Ceent 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 : 792

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

cent prisonbiers

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

cent orisonniers

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 prisonnniers

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 : 

Un berger a 10 moutons, ils meurent tous sauf 9, combien en reste-t-il ?

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