100 prisonniers sont condamnés à mort. Le directeur de la prison propose un challenge à nos prisonniers :
- il leur attribue à tous un numéro entre 1 et 100
- il installe dans son bureau une armoire avec 100 tiroirs, dans chacun desquels il met aléatoirement un et un seul numéro entre 1 et 100. Chaque numéro apparait une et une seule fois.
Il propose à chaque prisonnier de venir ouvrir 50 tiroirs de son bureau, pour regarder le numéro qui est dedans. Les prisonniers sont d'abord réunis pour élaborer une stratégie puis envoyer dans un ordre aléatoire dans le bureau. Une fois passés dans le bureau, les prisonniers ne peuvent pas communiquer entre eux, ni changer les numéros de place, ni laisser un tiroir ouvert, ni coller un chewing-gum sur l'interrupteur de la lampe... Ils ne verront jamais les autres prisonniers avant le jugement dernier.De deux choses l'une :
- Tous les prisonniers ont trouvé leur numéro en ouvrant les tiroirs auxquels ils avaient droit : ils sont tous graciés.
- Sinon, ils sont tous exécutés.
Un probabiliste dans le groupe des prisonniers dit : "aie aie aie ! On est mal : 1 chance sur 2^100 de s'en sortir". A-t-il vraiment raison ? N'y a-t-il pas un moyen d'augmenter cette probabilité ?(Indication : il existe une stratégie telle qu'ils aient une probabilité > 1-ln2 de s'en sortir. Ça parait vraiment surprenant mais c'est possible)

1

Réponses

Meilleure réponse !
2014-03-23T15:00:20+01:00


 un nombre de boites de 4, de 6 et de 8, je ne trouve pas de variation de la probabilité de trouver son numéro avant de dépasser la moitié.

Par exemple pour 6 boites :

Il y'a 6! répartitions possible des numéros au sein des boites

Admettons que l'individu ai le numéro 1.
Conformément à la stratégie énoncé par ming il va donc commencer par choisir la boite numéro 1 :

Il y'a donc 5! possibilités pour qu'il trouve du premier coup

Si il ne trouve pas du premier coup alors dans ce cas il y'a 4!*5 possibilités pour qu'il trouve au deuxième coup : si la boite est numéroté 2 il faut que le numéro 1 soit dans la deuxième boite.

Si il échoue il peut encore trouver au troisième essai : et là il y'a 5*4*3! répartitions qui permette ce dénouement.

Au total on trouve donc bien une probabilité de 1/2 qu'il trouve son numéro en appliquant cette stratégie.