Dans la prison des logiciens, on propose le jeu suivant à 100 prisonniers. On dispose les 100 prisonniers en file indienne, de sorte que chaque logicien peut voir les logiciens devant lui, mais pas ceux derrière lui. On place un chapeau noir ou blanc sur la tête de chacun d’entre eux, puis on demande tour à tour aux logiciens de deviner la couleur de leur chapeau.
On commence par demander à celui de derrière (celui qui voit 99 chapeaux), puis on remonte pour finir avec celui de devant (celui qui n’en voit aucun). Chaque logicien entend toutes les réponses précédentes.
Si un logicien trouve la couleur de son chapeau correctement, il est libéré. S’il ne trouve pas, il est condamné à mort.
Les logiciens ont le droit de se concerter avant le jeu afin d’établir une stratégie.
Les logiciens trouvent ensemble une stratégie afin de libérer au moins 99 prisonniers. Quelle est-elle ?
Hints
1Hint 1
Open this only if you want a small nudge before looking at the solutions.
Solutions
1Reveal solutionsAre you sure? Give it a try first.
Solution by AstroAure
On va malheureusement sacrifier le premier logicien. En effet, il peut donner une information qui permettra aux autres de savoir la couleur de leur chapeau.
Son rôle sera de dire "blanc" s’il y a devant lui un nombre pair de chapeaux blancs, et "noir" s’il y a un nombre impair.
Imaginons qu’il dise "blanc". Le deuxième logicien regarde alors devant lui :
- Soit il voit un nombre pair de chapeaux blancs et donc son chapeau doit être noir (sinon le premier aurait vu un nombre impair de chapeaux blancs).
- Soit il voit un nombre impair de chapeaux blancs et donc son chapeau doit être blanc.
Le troisième logiciens, ainsi que les suivants, ont alors juste à noter ces changements de parité et comparer la parité du nombre de chapeaux blancs devant eux avec celle attendue. Ils peuvent alors tous connaître la couleur de leur chapeau.
Au final, on sauve logiciens à coup sûr, et, avec un peu de chance, le premier en plus.