problème des chapeaux

problème des dérangements
problème de de Montmort

COMBINATOIRE
PROBABILITES

Plusieurs problèmes de probabilité ou de stratégie ont traditionnellement un « habillage » faisant intervenir des chapeaux.

1 – n personnes laissent leur chapeau à un vestiaire. En repartant, chaque personne reprend un chapeau au hasard. Quelle est la probabilité qu’aucun ne reprenne son propre chapeau ? C’est une des formulations du problème des rencontres, ou problème de Montmort (voir exercice 9 de http://exo7.emath.fr/ficpdf/fic00095.pdf , exercice 2 de http://perso.univ-rennes1.fr/jurgen.angst/enseignements/exo_velenik/PS_serie2.pdf )

Autre façon de poser la question : Montrer que la probabilité qu’aucune de ces personnes n’ait repris son propre chapeau est environ 1/e
Ou, plus simple : Dix hommes ont laissé leur chapeau au vestiaire. En reprenant un chapeau au hasard, quelle est la probabilité qu’une personne tombe sur son propre chapeau ? (voir http://villemin.gerard.free.fr/Puzzle/Chapeau.htm)

2 – Une deuxième catégorie de problèmes est la suivante :
On dispose de chapeaux de deux couleurs différentes. N personnes reçoivent chacune un chapeau dont il ne connaît pas la couleur mais il voit la couleur de tous les autres (ou bien seulement certains voient la couleur des autres chapeaux). Le problème est de trouver une stratégie qui permettra au plus grand nombre de trouver la couleur de son chapeau.
Suivant la difficulté recherchée pour le problème, il y a divers énoncés. En voici des exemples :
3 personnes sont placées en file indienne, sur la tête de chacun se trouve un chapeau tiré au hasard parmi 2 chapeaux noirs et 3 chapeaux blancs. Chacun voit les chapeaux des personnes qui se trouvent devant lui (le premier n’en voit aucun). On leur demande, sans se retourner de connaitre la couleur de leur chapeau… Après quelques secondes de silence, la première personne prend la parole et devine correctement la couleur de son chapeau. Quelle est la couleur de son chapeau et comment a-t-elle fait ? (voir
http://www.prise2tete.fr/forum/viewtopic.php?id=647 )
Le même existe avec deux chapeaux de chaque couleur

Ou encore : 100 personnes sont placées de telle façon que chacun voit tous les autres, chacune a un chapeau, qui est soit jaune, soit bleu. Personne ne peut voir la couleur de son propre chapeau, mais tout le monde voit les chapeaux des autres.
– une personne est désignée pour parler en premier, puis c’est le tour de la personne située à
sa gauche, puis la personne suivante à gauche, et ainsi de suite . . .
– chaque personne dit « jaune » ou « bleue » (éventuellement « je ne sais pas »), les autres entendent ce qui est dit, mais personne ne peut donner d’autre information.
La situation est étudiée avec prolongement jusqu’à une infinité de chapeaux et de couleurs sur http://www.cmapx.polytechnique.fr/~benaych/benaych.chapeaux.pdf