Les 10 prisonniers et les chapeaux

10 mathématiciens ont été emprisonnés et condamnés à mort.

Leurs sadiques bourreaux leurs laissent cependant une chance de s'en sortir :
Ils leurs expliquent qu'ils vont placer les prisonniers en file indienne et mettre sur la tête de chacun d'eux un chapeau d'une certaine couleur.
Chacun à leur tour, dans l'ordre qu'ils voudront, les prisonniers vont annoncer une couleur. Si c'est la couleur de son chapeau, le prisonnier sera alors gracié. Sinon, il sera exécuté.

Aucun prisonnier ne pourra voir quelle est la couleur de son propre chapeau.
En revanche, le prisonnier placé en dernière position pourra voir les chapeaux de ses 9 autres compagnons, le prisonnier en avant-dernière position verra les chapeaux des 8 autres, etc,...jusqu'au prisonnier en première position qui ne pourra malheureusement voir aucun des chapeaux.

Les chapeaux peuvent être de 3 couleurs différentes : bleu, blanc et rouge.
Il y a un nombre illimité de chapeau de chaque couleur.

Enfin, les bourreaux laissent quelques instants aux prisonniers pour mettre au point une "stratégie" pour se sauver.

Selon vous, combien de prisonniers pourront se sauver et quelle est la stratégie qui permet de faire gracier un maximum de prisonniers ?

Une stratégie qui permettrait de sauver les 10 prisonniers à coup sûr serait optimale, mais elle n'existe pas car le prisonnier situé en dixième position n'a aucune information sur la couleur de son chapeau étant donné que personne ne peut le voir et que le nombre de chapeau de chaque couleur est illimité. Il ne peut donc espèrer se sauver qu'une fois sur 3.

Il existe en revanche une stratégie qui permet de sauver à coup sûr les 9 autres prisonniers. Ils doivent agir de la manière suivante :

Ils parleront chacun à leur tour, en partant du prisonnier situé en dixième position jusqu'à celui en première position.
Le premier à parler, qui voit les 9 chapeaux devant lui, fera un rapide calcul en fonction des couleurs des chapeaux.
En associant par exemple 0 à la couleur bleu, 1 au blanc et 2 au rouge, il devra faire la somme de toutes les couleurs qu'il voit. Puis, il devra diviser la somme obtenue par 3 et, suivant le reste de la division, il annoncera une couleur : bleu si le reste est égal à 0, blanc si c'est 1 et rouge si c'est 2.

En faisant ainsi, il aura 1 chance sur 3 d'être sauvé, mais il permettra surtout à tous ses compagnons d'être gracié.

En effet, le prisonnier suivant, qui voit les chapeaux des 8 autres devant lui, réalise le même calcul avec les couleurs des 8 chapeaux. Puisqu'il connait le reste de la division par 3 de la somme des 8 chapeaux et du sien, il en déduit facilement la couleur qu'il a sur la tête.

Par exemple, si le prisonnier précédent a annoncé "rouge", il sait que le reste de la division est égal à 2. Calculant la somme des 8 chapeaux devant lui, admettons qu'il trouve 10. Il doit donc ajouter 1 pour que le reste de la division par 3 soit égal à 2 (11 = 3 x 3 + 2). 1 correspond à la couleur blanche, il en déduit que le chapeau qu'il porte est blanc.

Les prisonniers suivants effectuent le même raisonnement et arrivent donc tous à se sauver.

Reste à savoir quel malheureux prisonnier sera placé en 10ème position !