100 prisonniers sont alignés. Chaque prisonnier porte un chapeau noir ou blanc. Chacun peut voir les chapeaux devant lui, mais pas le sien. Ils doivent annoncer la couleur de leur propre chapeau, l’un après l’autre.
Ils peuvent élaborer une stratégie avant de commencer. Comment garantir qu’au moins 99 prisonniers donnent la bonne réponse ?
Le premier prisonnier utilise sa réponse pour transmettre une information codée, par exemple la parité du nombre de chapeaux noirs qu’il voit. Les 99 suivants utilisent cette information et les réponses précédentes pour déduire leur propre couleur.
Ainsi, au maximum un seul prisonnier se trompe.