Une perle rare

mardi 19 octobre 2010
par  M. Deleglise
popularité : 16%

Apres lecture vous allez vous dire que cet énoncé est incomplet ou faux, mais non.

Un directeur des études sadique, enferme les 400 élèves de la promotion
2006 de l’Ecole polytechnique dans un cachot. Dans un moment il viendra
chercher les élèves, un à un.
Chacun d’entre eux sera conduit dans une salle où sont alignés 400 coffres,
numérotés de 1 à 400.
Chaque coffre contient un matricule et un seul parmi les 400 matricules des élèves qui sont tous les entiers de 1 à 400.

L’élève a le droit d’ouvrir au maximum 200 coffres, de son choix,
jusqu’ à ouvrir le coffre contenant son matricule. S’il n’y parvient
pas il a échoué. Dans les deux cas il referme tous les coffres
ouverts, y compris celui ou se trouve son matricule, qu’il laisse
dans son coffre, au cas ou il aurait réussi.
Puis il quitte la salle d’examen, qui, après son départ est exactement
dans le même état que lorsqu’il y est entré. Une fois sorti il est dans l’impossibilité absolue de communiquer avec les élèves attendant leur
tour dans le cachot.

Mais, attention, ajoute le directeur, si l’un d’entre vous échoue toute la promotion sera recalée.

La situation semble désespérée. On s’attend à une probabilté de réussite
de l’ordre de 2^{-400}.
Pourtant l’un des élèves se lève et dit : « Non, en nous y prenant bien,
nous avons au moins 3 chances sur 10 de tous réussir. »

Quelle stratégie peut-il envisager ?

Ce problème a été posé sur un forum interne des élèves de l’Ecole
polytechnique. Mais il figure déja, merci à Pierre Lavaurs pour
cette information, dans un
livre
de jeux mathématiques de
Peter Winkler.
Voici sa solution.

Cette énigme est l’objet du problème ci-dessous. On y trouvera aussi
quelques questions supplémentaires, pretextes à réviser des notions de base de la théorie des probabilités.


Documents joints

Permutations et cycles
Permutations et cycles
Le problème des 400 coffres, corrigé
Le problème des 400 coffres, corrigé
Le problème des 400 coffres
Le problème des 400 coffres

Commentaires  (fermé)

Navigation