L'énigme des prisonniers

[g_h]

Hello !

Voici une petite énigme assez bluffante... !



On enferme 100 prisonniers, ayant des matricules de 1 à 100, dans un cachot (et ils ont tous un matricule différent). Les prisonniers sont donc tous ensemble et peuvent communiquer.
Le gardien vient les voir et leur dit :
"Derrière cette porte se trouve une salle avec 100 coffres alignés le long d'un mur.
Chaque coffre contient un numéro entre 1 et 100, chacun différent.

Je viendrai vous chercher un par un, et vous aurez le droit d'ouvrir au maximum 50 coffres.
Si au final, vous n'avez pas trouvé votre matricule dans l'un des coffres, alors je considèrerai que vous avez échoué.

Une fois votre matricule découvert, ou la limite des 50 coffres atteinte, vous sortirez de la salle, et vous ne pourrez, par aucun moyen, communiquer avec les autres prisonniers.

Vous devrez quitter la salle dans l'état même ou vous l'avez trouvée, tous les coffres refermés, contenant TOUS les numéros. Les numéros ne pourront PAS changer de coffre.

De plus, si l'un seul d'entre vous échoue, je considèrerai que tout le monde a échoué, et vous resterez tous en prison. Par contre, si tout le monde trouve son matricule, vous serez tous libres."




Sur ce, les prisonniers doivent donc réfléchir à une stratégie pour s'en sortir...

La stratégie la plus simple serait : chacun entre dans la salle, essaye 50 coffres plus ou moins au hasard. Il a donc 1 chance sur 2 de trouver son matricule. Les prisonniers ont donc... 1 chance sur 2¹⁰⁰ de s'en sortir, soit environ 7,9*10^-29%, ou encore la probabilité de gagner un peu plus de 4 fois au loto avec les 6 numéros

La question est : trouver une stratégie commune aux prisonniers pour que la probabilité qu'ils s'en sortent tous soit supérieure à ... 30% (non, ce n'est pas une blague )


Bon courage à tous

PS : cette énigme n'est pas de moi, mais je ne cite pas ma source pour l'instant, histoire de vous laisser le loisir de chercher !
-----

[g_h]

J'oubliais : vous pouvez remplacer le nombre 100 par 10, 1000 ou même par (8^12560!!!)!, ça ne change rien, il faut trouver une stratégie avec une probabilité de succès supérieure à 30% !

[invite35452583]

Bonjour,
tu as été voir là
C'était dur à trouver : elle est encore en 1ère page de cette rubrique.

[g_h]

Argh, zut, quel idiot, j'avais pas vu...

Désolé... !

[A voir en vidéo sur Futura]

[invite528b0bef]

Bonjour, comme sa qu pif je te dirais qu'il enleve tous les Zero de leurs pull

[invite528b0bef]

Re Bonjour, tu dit:

Une fois votre matricule découvert, ou la limite des 50 coffres atteinte, vous sortirez de la salle, et vous ne pourrez, par aucun moyen, communiquer avec les autres prisonniers.

Donc vola ma solution le premier prisonier va entrer et va ouvrir les coffre un apres l'autre dans l'ordre

Quand il ouvre le premier si c'est pas son N° il va crier Coffre N°1 porte le chiffre N°12 (car il n'a pas encore trouver sont N° et n'a pas atteint 50 coffres ) par exemple est continu juque a trouver sont N° ou atteindre les 50 coffres.

Le Prisonier N°2 va venir adméton que le Prisonier N°1 avais trouver le N°2 dans le coffre 30 il ne va pas ouvrir le coffre N°30 il va continuer la ou le prisonier N°1 a trouver sont N° et une fois qu'il arrive a 49 coffre il ouvre le coffre N°20 car il sais que c'est le bon puisque le Prisonier N°1 l'avais crier fort.

Et ainci de suite juque a la fin.

[danyvio]

Il semblerait (mais c'est difficile - pour moi - à démontrer au delà de 4 coffres + 4 prisonniers), qu'il faille choisir la stratégie préalable suivante : on partage les coffres en deux sous ensembles disjoints par exemple les coffres C1 à C50 et C51 à C100 ou toute autre combinaison.
Le prisonnier n° 1 ouvre le premier sous ensemble. S'il trouve son n°, le prisonnier suivant ouvre le deuxième sous ensemble. En effet, la proba de trouver son propre n° a diminué dans le sous ensemble 1 (puisqu'on a la certitude d'y trouver le n° 1) , et a corrélativement augmenté dans le sous ensemble 2. S'il trouve son n°, tous les coffres retrouvent une proba égale pour les n° suivants. On répète alors le processus, avec un sous ensemble de coffres identique (ou différent, peu importe, pourvu qu'il reste identique pendant la recherche des prisonniers de n° 1 + kn et 2 + kn.

Avec deux coffres et deux prisonniers, la stratégie est donc : le prisonnier 1 ouvre le coffre 1, et si tout va bien, le prisonnier 2 ouvre le coffre 2 avec la certitude de trouver son n°. Au final, cette stratégie offre un proba de 1/2 de survivre au lieu de 1/2*1/2=1/4 en laissant le seul hasard.
J'ai étendu à 4 coffres + 4 prisonniers, et je trouve une proba de1/6 de s'en tirer au lieu de 1/16, ce qui est bien.
Suis je sur la bonne voie ?