Problème : Les chapeaux

Même si les chapeaux sont un peu passés de mode, les problèmes des chapeaux restent des grands classiques.

Les chapeaux
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 ce concerter avant le jeu et d'établir une stratégie.
Quelle stratégie permet de minimiser le nombre de mort ?

Avant de donner la réponse à ce problème, en voici une version différente.

Les chapeaux (bis)
On propose maintenant un autre jeu à 100 autres prisonniers. Ils sont maintenant dans une salle, de sorte que chacun voit les chapeaux des autres, mais pas le sien. On demande ensuite à un logicien de deviner la couleur de son chapeau, et tout le monde entend sa réponse. Puis on sépare tous les logiciens, et on demande aux 99 autres logiciens de deviner la couleur de leur chapeau.
Quelle stratégie permet de sauver le maximum de logiciens ?

Indice : dans les deux cas, il existe une stratégie qui permet de les sauver tous, sauf éventuellement 1.

Évidemment, le premier à parler n'a aucune information, et quoiqu'il dise, il a une chance sur deux de trouver la couleur de son chapeau. On ne peut donc pas faire mieux que la stratégie décrite ci-dessous. Le premier à parler compte le nombre de chapeaux noirs parmi les 99 chapeaux qu'il voit. Si ce nombre est pair, il dit "blanc", et si ce nombre est impair, il dit "noir". Le deuxième à parler compte ensuite le nombre de chapeaux noirs devant lui, et peut comparer la parité de ce nombre avec la ce qu'à dit celui dernière lui. Si c'est la même parité, il sait qu'il a un chapeau blanc, et sinon qu'il a un chapeau noir. Puis le troisième déduit à partir des deux réponses précédentes la couleur de son chapeau, et ainsi de suite. Dans le deuxième problème, le premier logicien donne la parité du nombre de chapeaux blancs qu'il voit. Chacun peut ensuite déduire la couleur de son chapeau.

Pour les plus sportifs, vous pouvez essayer la version suivante, avec une infinité de logiciens et de chapeaux. On suppose l'axiome du choix.

Les chapeaux, cas dénombrable (***)
Dans la prison de Hilbert, il y a un nombre infini (dénombrable) de logiciens. On décide de les faire jouer au jeu des chapeaux en ligne. De nouveau, chacun voit tous les chapeaux devant lui (en nombre infini maintenant), et doit trouver la couleur du sien.
Quelle stratégie permet de sauver le maximum de logiciens ?

Indice : il existe de nouveau une stratégie qui permet de les sauver tous, sauf éventuellement 1. Pour finir, voici une dernière version, ma préférée.

Encore une infinité de chapeaux
Dans cette même prison, on propose un autre jeu. On met tous les logiciens dans une salle (toujours une infinité dénombrable), et chacun voit tous les autres chapeaux sauf le sien. On sépare ensuite les logiciens, et chacun doit trouver la couleur de son chapeau.
Les logiciens peuvent-ils trouver une stratégie avant le jeu qui permet de les sauver tous, sauf éventuellement un nombre fini d'entre eux ?

J'aime beaucoup cette dernière version, puisque cette fois-ci, aucune information n'est échangée, et pourtant, ils peuvent se sauver globalement.

La réponse est oui ! On commence par associer à chaque disposition de chapeaux un nombre entre 0 et 1 en base binaire $$ x = 0, a_1 a_2 \ldots a_n a_{n+1} \ldots , $$ où $a_k = 0$ si le k-ème chapeau est blanc, et $a_k = 1$ sinon. On introduit la relation d'équivalence $\sim$ sur $\mathbb{R}$ tel que $$ x \sim y \quad {\Longleftrightarrow} \quad x - y \quad \text{a un nombre fini de chiffres en base binaire}. $$ Autrement dit, $x \sim y$ si leur écriture en base binaire termine par la même infinité de chiffres. Il est facile de vérifier que $\sim$ est une relation d'équivalence. Pour chaque classe d'équivalence $C \in \mathbb{R} / \sim $, les logiciens se mettent d'accord sur un représentant $x_C \in C$ (ce qui est possible grâce à l'axiome du choix). Lors du jeu, puisque chaque logicien voit tous les chapeaux devant lui, chacun sait dans quelle classe d'équivalence $C$ appartient leur configuration $x$. De plus, si $n \in \mathbb{N}$ est le rang à partir duquel $x_m = C_m$ pour tout $m \ge $$, les $n-2$ premiers joueurs connaissent aussi l'entier $n$. Les $n-1$ premiers joueurs peuvent déduire la couleur de leur chapeau avec la stratégie précédente. Le reste des logiciens récitent les chiffres en base binaire de $x_C$ : la $k$-ème personne dira "blanc" si le $k$-ème chiffre en case binaire de $x_C$ est un $0$, et "noir" sinon. Dans la dernière version où les logiciens ne sont pas en ligne, le $k$-ème logicien donne la $k$-ème décimale de $C$. Comme $x$ et $C$ ne diffèrent que d'un nombre fini de décimales, seulement un nombre fini perd.