L'énigme des chapeaux alignés

Cette devinette captivante est un très grand classique des mathématiques récréatives, apparu sous sa forme moderne et épurée vers la fin du XXe siècle. Elle est par ailleurs très fréquemment posée lors des entretiens d'embauche dans les grandes entreprises technologiques de la Silicon Valley pour évaluer intelligemment la capacité des candidats à optimiser une communication restreinte.

Le tout dernier prisonnier de la file sacrifie son assurance de survie personnelle (il n'a qu'une seule chance sur deux d'avoir bon) en utilisant son unique mot pour transmettre à tous une règle de parité. Il compte les chapeaux noirs. Si le nombre est impair, il annonce « noir ». Le prisonnier suivant, voyant les chapeaux devant lui, peut alors immédiatement déduire la couleur exacte de son propre couvre-chef en comparant la parité annoncée avec ce qu'il voit. Et ainsi de suite, en cascade ininterrompue, jusqu'au tout premier homme de la file.

C'est une énigme absolument fascinante car elle montre avec une grande clarté comment transformer une simple devinette de survie en un véritable code binaire de transmission d'informations. Elle constitue une excellente introduction aux concepts fondamentaux des codes correcteurs d'erreurs en informatique.