Les 100 prisonniers

[radoude]

Bonjour à tous,

Voici un très beau problème que peut-être certains (beaucoup?) d'entre vous connaissent.
Je le poste néanmoins pour le plaisir de ceux qui ne le connaitraient pas.

100 prisonniers portant des dossards numérotés de 1 à 100 sont condamnés à mort.
On leur explique qu'ils seront graciés si ils réussissent TOUS l'épreuve suivante:

L'un après l'autre, on les fait entrer dans une pièce avec 100 coffres numérotés de 1 à 100.

Dans chaque coffre se trouve un numéro de 1 à 100 et les numéros dans les coffres sont tous différents.

Le prisonnier dans la pièce a le droit d'ouvrir un maximum de 50 coffres différents.

S'il trouve dans un des coffres ouverts le numéro de son dossard, il a réussi l'épreuve.

Quelle que soit la réussite ou l'échec de l'épreuve, on l'isole des autres prisonniers et on fait entrer le suivant pour la même épreuve. (Les coffres ont bien entendu été refermés!)

Les prisonniers seront graciés si tous réussissent l'épreuve.(Si un seul échoue, tout le monde y passe!)

Avant le début de l'épreuve ils peuvent mettre au point une stratégie commune.

La question:

Il existe une stratégie qui optimise la probabilité qu'ils soient graciés. Quelle est cette stratégie et quelle est la probabilité qu'ils soient graciés?

Pour les très très forts, la question annexe (à laquelle je suis absolument incapable de répondre!):

Prouver que cette stratégie est la meilleure possible.

Voilà, Bon amusement. (La réponse est surprenante relativement à P=1/2^100 qui serait celle de la réussite si les coffres étaient ouverts au hasard!)

[Sylviel]

Excellent petit problème !

Si quelqu'un veut la solution, et la preuve d'optimalité on peut la trouver ici :
http://www.maths.tcd.ie/~onash/pity_the_prisoners_files/locker-problem.pdf