Forum de mathématiques - Bibm@th.net

Boody a vu juste, l'un des prisonnier compte le nombre de chapeaux blancs parmi les autres. Si ce nombre est pair il est convenu qu'il dise "blanc" sinon il dit "noir".
Il y a une possibilité que ce premier prisonnier meurt mais les autres ne mourront pas.
En effet, un autre prisonnier a entendu "blanc" ou "noir" dit par le premier prisonnier. Il regarde le nombre de chapeaux blancs parmi les autres prisonniers excépté lui même (car il ne connait pas la couleur de son propre chapeau) et excepté le premier prisonnier.
Si la parité observée est la même que la parité annoncée par le premier prisonnier c'est que lui même a un chapeau noir, sinon c'est qu'il a un chapeau blanc.

Selon cette stratégie $V=1$ car dans le pire des cas, seul le premier prisonnier se fait pendre. NB : on peut vérifier assez facilement que $V=0$ est impossible (car le premier prisonnier à parler aura toujours une possibilité de se tromper).

Supposons $N$ pair pour plus de simplicité. Une stratégie est la suivante : les prisonniers se divisent en deux groupes égaux, l'un des deux groupes part de l'hypothèse que dans la pièce il y a un nombre pair de chapeaux blancs, l'autre groupe part de l'hypothèse qu'au total il y a un nombre impair de chapeaux blanc. L'un des deux groupes a forcément raison.
Les prisonniers disent alors la couleur de leur chapeau suivant un raisonnement similaire aux suivants :
"Si je vois un nombre impair de chapeaux blancs et que je suppose qu'il y a un nombre total impair de chapeaux blancs c'est que moi même j'ai un chapeau noir."
"Si je vois un nombre pair de chapeaux blancs et que je suppose qu'il y a un nombre total impair de chapeaux blanc, c'est que moi même j'ai un chapeau blanc".
etc...

Avec cette stratégie exactement l'un des deux groupes sera sauf, l'autre sera éxécuté et donc $V=N/2$ (je vous laisse adapter au cas $N$ impair).

Pourquoi cette stratégie est optimale ?
Un argument du au hasard :
Supposons que chaque chapeau soit noir ou blanc avec proba 1/2 indépendament les uns des autres.
Une stratégie est la donnée de $(f_i)_{1\leq i \leq N}$ avec $f_i : \{0,1\}^{n-1}\to\{0,1\}$
Notons $X_i\in \{0,1\}$ la couleur (aléatoire) du chapeau du prisonnier $i$.
La stratégie consiste à dire que $i$ répond $f_i(X_1,X_2,\dots,\hat{X_i},\dots,X_N)$.
Ainsi $X_i$ est indépendant de $f_i(X_1,X_2,\dots,\hat{X_i},\dots,X_N)$. Et donc $\mathbb{P}(i \text{ survit})=1/2$.
Finalement notons $V$ le nombre de victimes, nous avons par linéarité de l'espérance $\mathbb{E}[V] = N/2$ (cela est valable quelque soit la stratégie).
Il est donc impossible d'avoir $V<N/2$ presque surement, ce qui prouve l'optimalité de la stratégie décrite ci dessus.
(je vous laisse encore une fois adapter au cas $N$ impair).

Supposons qu'il y a $k\geq 2$ couleurs possibles pour les chapeaux. On travaille alors dans $\mathbb{Z}/k\mathbb{Z}$. Chaque couleur est représentée par une classe de $\mathbb{Z}/k\mathbb{Z}$.
Notons $c_1,\dots,c_N$ les couleurs des chapeaux des prisonniers de $1$ à $N$ (ainsi $c_i \in \mathbb{Z}/k\mathbb{Z}$).
Le premier prisonnier dit la couleur correspondant à $c := \sum_{j=2}^N c_j$.
Il se trompe peut-être mais les prisonniers suivants ne tromperont pas.

En effet un prisonnier suivant connait $c$ (il a entendu la réponse du premier prisonnier).
Le prisonnier $i\geq 2$ dit alors la couleur $c - \sum_{j=2, j\neq i}^Nc_j = c_i$ et il trouve bien sa couleur à coup sûr.

Ainsi encore une fois $V=1$.

Soit $C$ un ensemble (infini ou non), si on suppose l'axiome du choix, alors il existe un groupe commutatif $G$ en bijection avec $C$.
(Autrement dit , pour tout cardinal il existe un groupes commutatif qui a ce cardinal).
$\textbf{Preuve: }$
Si $C$ est fini de cardinal $n$, alors $G = \mathbb{Z}/n\mathbb{Z}$ est un candidat qui fonctionne.
Supposons $C$ infini,
Notre candidat est $\mathbb{Z}^{(C)} := \{f : C \to \mathbb{Z} | \sharp\{c\in C, f(c)\neq 0\}<\infty\}$.
Autrement dit un élément de $\mathbb{Z}^{(C)}$ est juste une fonction de $C$ dans $\mathbb{Z}$ qui est nulle sauf éventuellement en nombre fini de points.
Il s'agit bien d'un groupe commutatif pour l'addition usuelle des fonctions à valeurs dans $\mathbb{Z}$.

Reste à voir que $C$ est en bijection avec $\mathbb{Z}^{(C)}$.
Clairement on a $C$ s'injecte dans $\mathbb{Z}^{(C)}$ (à $c$ on associe $\delta_c$).
Par ailleurs on a $Card(\mathbb{Z}^{(C)}) \leq Card(\cup_{n\geq 0} \mathbb{Z}^n\times C^n) \leq Card(\mathbb{Z}\times \cup_{n\geq 0}C^n) \leq Card(C^2) \leq Card(C)$.
On conclut avec Cantor-Bernstein.
NB : on a utilisé l'axiome du choix et le fait que $C$ est infini pour dire que $Card(C^n)=Card(C)$, et aussi on a utilisé le fait que $C$ est infini pour dire que $Card(\mathbb{Z}^n) = Card(\mathbb{Z}) \leq Card(C)$ (là on utilise juste l'axiome du choix dnb pour la dernière inégalité, il me semble).

Notons $C$ l'ensemble des couleurs, on suppose par le lemme que $C$ est muni d'une structure de groupe commutatif (autrement dit on peut faire des sommes finies d'éléments de $C$ et obtenir un élément de $C$).
La solution est alors exactement la même que dans la variante 2, et on trouve toujours $V=1$.

$I$ est l'ensemble (infini) des prisonniers.
$C$ est l'ensemble des couleurs (qu'on suppose muni d'une structure de groupe abélien par le lemme).
Une configuration est un $c= (c_i)_{i\in I} \in C^I$.
On introduit la relation d'équivalence suivante sur les configurations :
$$c\sim c' \Leftrightarrow \sharp \{i \in I, c_i \neq c'_i\}<\infty.$$
Ainsi deux configurations sont équivalentes si elles ne différèrent au plus que sur un ensemble fini de prisonniers.

Par l'axiome du choix on peut choisir pour chaque classe d'équivalence un représentant dans $C^I$.
Autrement dit, on a une application $F : C^I \to C^I$ tel que $\forall c \in C^I, F(c)\sim c, \forall c_1,c_2, \text{ }c_1\sim c_2 \Leftrightarrow F(c_1)=F(c_2).$

La stratégie est alors la suivante. On choisit un prisonnier en particulier (le premier à parler), on le note $i_0\in I$.
Le prisonnier $i_0$ observe $(c_i)_{i\in I\setminus \{i_0\}}$, il pose alors $c_{i_0}=0$ (le $0$ du groupe $C$). Et obtient donc un $c=(c_i)_{i\in I}$. Il obtient alors un $\tilde{c}=F(c)$. Par définition on sait que $\tilde{c}\sim c$ et donc $\tilde{c}$ et $c$ diffèrent au plus en un nombre fini de prisonnier.

Le prisonnier $i_0$ dit alors au gardien la couleur : $\sum_{i\in I\setminus \{i_0\}}c_i-\tilde{c}_i$.
Cette somme est bien définie car il s'agit en fait d'une somme finie et $C$ est bien un groupe commutatif.

Un prisonnier $j\neq i_0$, entend cette information $\sum_{i\in I\setminus \{i_0\}}c_i-\tilde{c}_i$.
Et ce prisonnier voit $(c'_i)_{i\in I\setminus \{j\}}$. En posant $c'_j=0$ (momentanément), il voit donc un $(c'_i)_{i\in I}$.
Il calcule alors $\tilde{c}':=F((c'_i)_{i\in I})$. Il obtient en fait $\tilde{c}'=\tilde{c}$ car les deux séquences $(c_i)_i$ et $(c'_i)_i$ ne diffèrent  qu'en deux points au plus (en $i_0$ et en $i$), et sont donc équivalentes (pour $\sim$).

Finalement, le prisonnier $j$ dit alors $\left(\sum_{i\in I\setminus \{i_0\}}c_i -\tilde{c}_i \right)- \left(\sum_{i\in I\setminus \{i_0,j\}}c_i-\tilde{c}_i\right)+\tilde{c}_{j}$ et tombe bien sur sa couleur !

Ainsi $V=1$ encore une fois !

Avec la même relation d'équivalence $\sim$ que pour la variante 4.
Un prisonnier $j$ calcule $\tilde{c}=F((c_i)_{i\in I})$ (où il a remplacé $c_j$ qu'il ne peut pas voir par $0$).
Notons que $\tilde{c}$ obtenu ne dépend pas de $i$.
Et par ailleurs, $\tilde{c}\sim (c_i)_{i\in I}$.
Chaque prisonnier dit alors $\tilde{c}_i$, et seul un nombre fini de prisonniers va se tromper.

1. 
La parité sauvera tout le monde sauf le premier à parler qui répond (par exemple) noir s'il voit un nombre pair de chapeau blanc et blanc sinon.
Si on voit la même parité de chapeau blanc que le premier à parler (en ignorant son chapeau à lui) on répond la couleur qu'il a annoncé sinon on répond l'autre couleur.