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 prisonnoers

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 prsionniers

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

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

Cetn prisonniers

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

Cent prsionniers

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

cent prusonniers

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 pisonniers

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