Les maths et le prisonnier

Dans une contrée lointaine, un groupe de 100 mathématiciens a été pris en otage.
Ils sont stockés dans une prison isolée et mis sous la surveillance d'un maton pervers.
Après 183 jours de captivité, la décision est prise de fermer leur prison, mais aucune instruction n'est donnée concernant les prisonniers.

Morts ou Libres, le gardien pervers doit prendre lui-même la décision.
Il décide de confier le sort des mathématiciens ... au hasard.

Il aménage une grande pièce en y disposant 100 casiers numérotés de 1 à 100. Il prend 100 morceaux de papier et écrit sur chacun d'eux l'identité de l'un des prisonniers. Il dispose ensuite au hasard un papier dans chaque casier, puis ferme chaque casier.

Le protocole est le suivant :
* Le gardien va chercher un prisonnier au hasard.
* Il le conduit à la "salle des casiers".
* Le prisonnier a le droit d'ouvrir 50 casiers de son choix :
- s'il ne trouve pas son nom, les 100 sont exécutés.
- s'il trouve son nom, il est conduit dans une salle, les casiers sont tous refermés, et le gardien va chercher le prisonnier suivant.

Si tous les prisonniers trouvent leur nom, ils sont libérés.
Si un seul échoue, ils sont tous exécutés.

Quelle tactique mettre en place pour arriver au meilleur pourcentage de survie ?
Quelles sont leurs chances de survie ?

Deux questions pour ce problème. La première nécessite de la logique, la deuxième des mathématiques.

Est-ce que les prisonniers peuvent communiquer avant et/ou après leur passage devant les casiers?

Salut à tous,

Au lieu d'effectuer 100 tirages aléatoires indépendants les prisonniers peuvent déjà faire un tirage de deux paquets de 50 casiers qu'ils ouvriront alternativement ce qui augmente la proba de réussir d'un facteur supérieur à 12.

Je cherche autre chose..... A+

limbo a écrit:

Est-ce que les prisonniers peuvent communiquer avant et/ou après leur passage devant les casiers?

Non, aucune communication possible.
Le maton conduit celui qui a tenté sa chance dans la pièce receptacle, et va ensuite chercher le suivant.

pour le meme resultat, on peut dire aux 50 premiers prisoniers d'ouvrir les 50 premiers casiers et aux 50 derniers de finir le boulot ...
dans les deux cas, ça offre un chance sur 10^29 aux prisoniers de survivre ... c'est plus que le loto

baron de roc a écrit:

Salut à tous,

Au lieu d'effectuer 100 tirages aléatoires indépendants les prisonniers peuvent déjà faire un tirage de deux paquets de 50 casiers qu'ils ouvriront alternativement ce qui augmente la proba de réussir d'un facteur supérieur à 12.

Je cherche autre chose..... A+

C'est vrai, ça augmente les chances (je pense même que le facteur est bien supérieur à 12).
Mais si j'ai bien suivi, pour être sauvés il faudrait que les cinquante casiers choisis par le premier groupe correspondent aux prisonniers "pairs" et les cinquante autres aux prisonniers "impairs", sans le moindre droit à l'erreur, sinon couic !

En pourcentage, ça donne quoi comme "chance" d'être sauvés ?

Bonnes recherches baron, et n'oublie pas que ce sont des mathématiciens qui sont prisonniers.

J'ai fais le meme calcul que baron, ça multiple les chances par 12.56 (si mes calculs sont justes)

godisdead a écrit:

pour le meme resultat, on peut dire aux 50 premiers prisoniers d'ouvrir les 50 premiers casiers et aux 50 derniers de finir le boulot ...
dans les deux cas, ça offre un chance sur 10^29 aux prisoniers de survivre ... c'est plus que le loto

Exact Olivier pour la première phrase.
Je suis un peu plus sceptique sur les 10^29, je pencherais davantage pour environ 10^17. Tu peux expliquer ton calcul ?


PS : j'ai oublié de préciser : ce n'est pas forcément un vendredi 13

ours blanc a écrit:

Quelles sont leurs chances de survie ?

D'aucun vous diront qu'ils peuvent augmenter leur chance de survie jusqu'à environ 30,68% en utilisant une stratégie de numérotation ingénieuse mais néanmoins insuffisante pour être sûr de sauver tout le monde.

Leur chance de survie est d'environ 100% s'ils suivent la procédure suivante:

• Ils demandent chacun une entrevue confidentielle avec le directeur de la prison qui ne pourra leur refuser ce droit avant une probable exécution capitale.
  
• Prétextant être maltraités par leurs collègues car ils ont un nom à consonance étrangère, ils demandent alors de publier un changement de nom dans le journal officiel de la prison, chacun trouvant que le nom "John Smith" lui ira à ravir et ne lui posera pas de problème de discrimination.
  
• Ensuite, ils font un dossier de demande de changement de nom qu'ils adressent au Garde des Sceaux ou au procureur de la République du tribunal de grande instance du domicile, dans lequel ils n'oublieront pas de fournir:
  "un exemplaire de chacun des journaux dans lesquels l'(les) annonce(s) légale(s) a (ont)été publiée(s),
  la copie intégrale de l'acte de naissance de chaque intéressé,
  la copie d'une pièce prouvant la nationalité,
  le bulletin numéro 3 du casier judiciaire,
  une bonne bouteille de vin rouge et une boîte de pralinés,
  une requête personnelle sur papier libre, adressée au Garde des Sceaux. Elle doit être signée et comprendre les raisons de l'abandon du nom d'origine et les raisons du choix du nom demandé. Tout document établissant le bien fondé de cette demande doit être joint pour l'appuyer."
  
• Ainsi le jour du tirage au sort des casiers, tous les prisonniers s'appelant John Smith, ils ne leur faudra qu'un casier pour être sûr que leur nom soit écrit dedans et ils seront tous sauvés !!!

Fred

ours blanc a écrit:

godisdead a écrit:

pour le meme resultat, on peut dire aux 50 premiers prisoniers d'ouvrir les 50 premiers casiers et aux 50 derniers de finir le boulot ...
dans les deux cas, ça offre un chance sur 10^29 aux prisoniers de survivre ... c'est plus que le loto

Exact Olivier pour la première phrase.
Je suis un peu plus sceptique sur les 10^29, je pencherais davantage pour environ 10^17. Tu peux expliquer ton calcul ?


PS : j'ai oublié de préciser : ce n'est pas forcément un vendredi 13

Le premier prisonier a 50 chances sur 100 d'avoir son nom ...
le deuxième a 50 chances sur 99
le troisième a 49 chances sur 98
le quatrième a 49 chances sur 97
le cinquième a 48 chances sur 96
ect ...
l'avant dernier a 1 chance sur 2
et le dernier est sur de sortir en vie

ça c'est la theorie de baron

Pour la mienne,
le premier a 50 chances sur 100
le deuxième a 49 chances sur 99
le troisième a 48 chances sur 98
ect ...
le cinquantieme a 1 chance sur 51, c'est lui le plus malchanceux du tas et s'il voit son nom, tout le monde est sauvé ...

En maths, ça donne 1 chance sur (50! / (100!/50!)) ... D'ailleurs, on voit bien que la première theorie donne le meme resultat puisque la formule serait 50! * 50! / 100!
je me suis planté qq part ???

godisdead a écrit:

le deuxième a 50 chances sur 99

le deuxième a 49 chances sur 99

Euh pourquoi sur 99? le casier du premier est remis à sa place non?

Fred

Fred76 a écrit:

ours blanc a écrit:

Quelles sont leurs chances de survie ?

D'aucun vous diront qu'ils peuvent augmenter leur chance de survie jusqu'à environ 30,68% en utilisant une stratégie de numérotation ingénieuse mais néanmoins insuffisante pour être sûr de sauver tout le monde.

Leur chance de survie est d'environ 100% s'ils suivent la procédure suivante:

• Ils demandent chacun une entrevue confidentielle avec le directeur de la prison qui ne pourra leur refuser ce droit avant une probable exécution capitale.
  
• Prétextant être maltraités par leurs collègues car ils ont un nom à consonance étrangère, ils demandent alors de publier un changement de nom dans le journal officiel de la prison, chacun trouvant que le nom "John Smith" lui ira à ravir et ne lui posera pas de problème de discrimination.
  
• Ensuite, ils font un dossier de demande de changement de nom qu'ils adressent au Garde des Sceaux ou au procureur de la République du tribunal de grande instance du domicile, dans lequel ils n'oublieront pas de fournir:
  "un exemplaire de chacun des journaux dans lesquels l'(les) annonce(s) légale(s) a (ont)été publiée(s),
  la copie intégrale de l'acte de naissance de chaque intéressé,
  la copie d'une pièce prouvant la nationalité,
  le bulletin numéro 3 du casier judiciaire,
  une bonne bouteille de vin rouge et une boîte de pralinés,
  une requête personnelle sur papier libre, adressée au Garde des Sceaux. Elle doit être signée et comprendre les raisons de l'abandon du nom d'origine et les raisons du choix du nom demandé. Tout document établissant le bien fondé de cette demande doit être joint pour l'appuyer."
  
• Ainsi le jour du tirage au sort des casiers, tous les prisonniers s'appelant John Smith, ils ne leur faudra qu'un casier pour être sûr que leur nom soit écrit dedans et ils seront tous sauvés !!!

Fred

un mot, un seul, j' ADORE

Chaque mathématicien a:
1/100 +1/99 +1/98+1/97+...........1/53+1/52+1/51 chances d'avoir son nom donc 0,6681 chance de trouver son nom.
Donc pour 100 mathématiciens on a 0,6681^100 soit 5,82 10^-17 chances de s'en sortir.

Bon à partir de là.......y-a-t-il un autre moyen d'augmenter ses chances?

Faites le moi savoir..........pour le loto

Fred76 a écrit:

godisdead a écrit:

le deuxième a 50 chances sur 99

le deuxième a 49 chances sur 99

Euh pourquoi sur 99? le casier du premier est remis à sa place non?

Fred

Si le deuxième n'est pas encore mort, c'est que le premier prisonier a trouvé son nom ...
S'il l'a trouvé dans les 50 premiers casiers, il n'y a plus que 49 casiers inconnus dans les 50 premiers, comme il regarde les 50 derniers, il a 50 chances sur 50 + 49 de trouver le bon ...

Dans le deuxième cas, on sait que le nom du premier est dans les 50 premiers casiers, donc il ne reste plus que 49 chances de trouver parmis 99 inconnus ... (le 50ième casier qu'il va ouvrir est forcement celui qui a le nom du premier ...)

limbo a écrit:

Chaque mathématicien a:
1/100 +1/99 +1/98+1/97+...........1/53+1/52+1/51 chances d'avoir son nom donc 0,6681 chance de trouver son nom.
Donc pour 100 mathématiciens on a 0,6681^100 soit 5,82 10^-17 chances de s'en sortir.

Bon à partir de là.......y-a-t-il un autre moyen d'augmenter ses chances?

Faites le moi savoir..........pour le loto

Je ne comprends pas ta formule ...
Ou plutot, imagine que les mathematiciens doivent ouvrir 70 boites ...
Tu ferais 1/100+1/99+...1/32+1/31 ... 1,21 chance de trouver son nom

En fait, j'ai compris ton erreur, (peut-etre la meme qu'ours blanc)
On n'ajoute pas les chances de victoire sans prendre en compte les echecs ...
le premier tirage, tu as 1/100 de chance trouver le nom
le deuxième tirage, tu as 1/99 de chance de trouve le nom

Donc au bout de deux tirages, tu as 1/100 + 99/100 * 1/99 de trouver ton nom ce qui correspond bien à 2/100 ...
bref, 50 tirages te donnera une chance sur 2 de trouver ton nom ... ni plus, ni moins ...

godisdead a écrit:

En fait, j'ai compris ton erreur, (peut-etre la meme qu'ours blanc)
On n'ajoute pas les chances de victoire sans prendre en compte les echecs ...
le premier tirage, tu as 1/100 de chance trouver le nom
le deuxième tirage, tu as 1/99 de chance de trouve le nom

Donc au bout de deux tirages, tu as 1/100 + 99/100 * 1/99 de trouver ton nom ce qui correspond bien à 2/100 ...
bref, 50 tirages te donnera une chance sur 2 de trouver ton nom ... ni plus, ni moins ...

En fait, j'y suis allé à l'emporte pièce en me disant "pour chaque prisonnier qui entre dans la pièce, il a une chance sur deux de trouver son nom". (ce qui est faux puisque je ne tiens pas compte du fait que le précédent a gagné)
Puis : "si les 50 premiers ont trouvé leur nom, pas la peine d'aller plus loin"
D'où une proba de (1/2)^50.

Je fais amende honorable, vous avez raison !

godisdead a écrit:

En fait, j'ai compris ton erreur, (peut-etre la meme qu'ours blanc)
On n'ajoute pas les chances de victoire sans prendre en compte les echecs ...
le premier tirage, tu as 1/100 de chance trouver le nom
le deuxième tirage, tu as 1/99 de chance de trouve le nom

Donc au bout de deux tirages, tu as 1/100 + 99/100 * 1/99 de trouver ton nom ce qui correspond bien à 2/100 ...
bref, 50 tirages te donnera une chance sur 2 de trouver ton nom ... ni plus, ni moins ...

Oui tu as tout a fait raison, les probas n'ont jamais été mon point fort..

godisdead a écrit:

Fred76 a écrit:

godisdead a écrit:

le deuxième a 50 chances sur 99

le deuxième a 49 chances sur 99

Euh pourquoi sur 99? le casier du premier est remis à sa place non?

Fred

Si le deuxième n'est pas encore mort, c'est que le premier prisonier a trouvé son nom ...
S'il l'a trouvé dans les 50 premiers casiers, il n'y a plus que 49 casiers inconnus dans les 50 premiers, comme il regarde les 50 derniers, il a 50 chances sur 50 + 49 de trouver le bon ...

Dans le deuxième cas, on sait que le nom du premier est dans les 50 premiers casiers, donc il ne reste plus que 49 chances de trouver parmis 99 inconnus ... (le 50ième casier qu'il va ouvrir est forcement celui qui a le nom du premier ...)

nounours chat blanc a écrit:

- s'il ne trouve pas son nom, les 100 sont exécutés.
- s'il trouve son nom, il est conduit dans une salle, les casiers sont tous refermés, et le gardien va chercher le prisonnier suivant.

Donc, ils peuvent essayer de se répartir les casiers pour limiter les dégâts mais bon :

Le 1er entre dans la pièce aux casiers : a 1 chance sur 2 (50 sur 100) de trouver son nom.

S'il ne l'a pas trouvé, ils sont tous éxécutés et voilà !
S'il l'a trouvé, le gardien, referme tous les casiers vient chercher un autre prisonnier : donc tous ceux qui restent savent que le 1er nom a été trouvé et s'il savent quels sont casiers qui ont été ouverts, euhhh, je ne suis pas certaine que ça change quelque chose à ce stade.
Si le 2° prisonnier trouve son nom (1 chance sur 2), les autres peuvent respirer quelques minutes de plus, mais ...

Au bout du compte chaque prisonnier a 1 chance sur 2.

À moins qu'ils aient tous un bout de craie dans la poche et qu'ils cochent le casier sur lequel ils ont trouvé leur nom sans que le gardien dise rien. Et si le gardien ne dit vraiment rien, tant qu'à faire autant écrire sur chaque casier le nom trouvé dedans ... *afro*

j'arrive fred ne cours pas trop vite

J'en reste à ma première proposition, qui était sans doute la meilleure !

Fred

Fred76 a écrit:

ours blanc a écrit:

Quelles sont leurs chances de survie ?

D'aucun vous diront qu'ils peuvent augmenter leur chance de survie jusqu'à environ 30,68% en utilisant une stratégie de numérotation ingénieuse mais néanmoins insuffisante pour être sûr de sauver tout le monde.

Tout a fait juste Fred ! Tu l'a calculé ou pompé sur internet ? Surprenant n'est-ce pas la puissance des mathématiques ?

Fred76 a écrit:

Leur chance de survie est d'environ 100% s'ils suivent la procédure suivante:

• Ils demandent chacun une entrevue confidentielle avec le directeur de la prison qui ne pourra leur refuser ce droit avant une probable exécution capitale.
  
• Prétextant être maltraités par leurs collègues car ils ont un nom à consonance étrangère, ils demandent alors de publier un changement de nom dans le journal officiel de la prison, chacun trouvant que le nom "John Smith" lui ira à ravir et ne lui posera pas de problème de discrimination.
  
• Ensuite, ils font un dossier de demande de changement de nom qu'ils adressent au Garde des Sceaux ou au procureur de la République du tribunal de grande instance du domicile, dans lequel ils n'oublieront pas de fournir:
  "un exemplaire de chacun des journaux dans lesquels l'(les) annonce(s) légale(s) a (ont)été publiée(s),
  la copie intégrale de l'acte de naissance de chaque intéressé,
  la copie d'une pièce prouvant la nationalité,
  le bulletin numéro 3 du casier judiciaire,
  

Ah la la Fred, je pensais pourtant que "contrée lointaine" suffisait à imaginer une république banannière digne d'un pays comme ... comme ... ben la France me semble-t-il ?
Ok,ok

Ah oè j'avais pas lu le "contrée lointaine" !

Bof c'est pas parce que c'est loin que c'est différent !


Fred

C'est effectivement très surprenant comme énigme !

Je dois avouer que, ne voulant pas passer toute la journée à essayer de la résoudre (elle m'intriguait tellement !), je suis allé voir si je trouvais pas une petite explication ailleurs !

Et j'ai essayé de comprendre l'explication pendant la moitié de la journée !!!!

Fred

Fred76 a écrit:

C'est effectivement très surprenant comme énigme !

Je dois avouer que, ne voulant pas passer toute la journée à essayer de la résoudre (elle m'intriguait tellement !), je suis allé voir si je trouvais pas une petite explication ailleurs !

Et j'ai essayé de comprendre l'explication pendant la moitié de la journée !!!!

Fred

Alors petite indication pour comprendre l'explication :
Si ce n'est pas déjà fait, il faut que tu t'introduises à la notion de groupes, et plus particulièrement à la décomposition des permutations en cycles. Ca c'est pour le principe.
Ensuite, pour le calcul, ce sont les séries je crois qu'il faut revoir.

ours blanc a écrit:

Fred76 a écrit:

C'est effectivement très surprenant comme énigme !

Je dois avouer que, ne voulant pas passer toute la journée à essayer de la résoudre (elle m'intriguait tellement !), je suis allé voir si je trouvais pas une petite explication ailleurs !

Et j'ai essayé de comprendre l'explication pendant la moitié de la journée !!!!

Fred

Alors petite indication pour comprendre l'explication :
Si ce n'est pas déjà fait, il faut que tu t'introduises à la notion de groupes, et plus particulièrement à la décomposition des permutations en cycles. Ca c'est pour le principe.
Ensuite, pour le calcul, ce sont les séries je crois qu'il faut revoir.

Oè j'ai quand même fini par comprendre l'explication. Enfin le calcul je l'ai pas fait: ça doit quand même être assez compliqué, ça fait trop longtemps que j'ai plus fait ce genre de calcul.

Fred