Prisonniers

Énoncé

100 prisonniers sont chacun dans leur cellule, surveillés par le gardien de la prison. Parfois, le gardien appelle un prisonnier au hasard, l'emmène dans une salle secrète, puis le raccompagne à sa cellule. La salle secrète contient une lumière, qui est éteinte au début. Un prisonnier entrant dans la salle secrète a le droit d'allumer ou d'éteindre la lumière. Quelle stratégie les prisonniers peuvent-ils établir pour que, à un moment donné, un prisonnier comprenne que tous les prisonniers sont passés dans la salle secrète ? Les prisonniers ont le droit de communiquer pour établir leur stratégie au début, mais plus quand le jeu commence.

Solution

La stratégie consiste à donner à un prisonnier le rôle de compteur. Les autres prisonniers se signalent à lui en allumant la lumière. Plus précisément, lorsqu'un prisonnier qui n'est pas compteur arrive dans la salle secrète, s'il trouve la lumière éteinte et qu'il ne l'a encore jamais allumée, alors il l'allume. Le compteur, lui, lorsqu'il trouve la lumière allumée, l'éteint et retient qu'il y a un nain en plus qui est passé dans la salle. C'est finalement le compteur qui finit par comprendre que tous les prisonniers sont passés dans la salle secrète.