Des prisonniers et des chapeaux

Izolg

Bonjour
Vous connaissez peut être l'énigme des N prisonniers avec les chapeaux noirs et blanc.

Description de l'expérience :

Pour faire simple on se donne $N=2n\geq 2$ prisonniers. Chaque prisonnier reçoit un chapeau noir ou blanc. Chaque prisonnier voit les couleurs des chapeaux des autres mais pas la couleur de son propre chapeau. Puis, on demande à chaque prisonnier de dire ce qu'il pense être la couleur de son chapeau. (Les prisonniers n'entendent pas les réponses des autres). Un prisonnier qui répond juste est libéré, un prisonnier qui répond mal est pendu.

Les prisonniers étaient au courant en avance de cette "expérience". Ils ont donc pu décider au préalable d'une stratégie.

L'énigme originale est de trouver une stratégie qui permet à exactement la moitié des prisonniers de survivre (quelque soit la distribution des chapeaux). Une solution  par exemple repose sur le fait suivant : si un prisonnier connaît la parité du nombre total de chapeaux blancs, alors en observant le chapeau des autres il en déduit la couleur de son chapeau. Les prisonniers se séparent donc en deux groupes équilibrés. Le premier groupe prend l'hypothèse que le nombre total de chapeau blanc est pair, et l'autre groupe suppose que le nombre total de chapeau blanc est impair. Exactement l'un des deux groupes va survivre.

Description du modèle :

Étant donné $\omega \in \{0,1\}^N$ une distribution des chapeaux ($0$ pour noir, et $1$ pour blanc), et une stratégie $F : \{0,1\}^N \to \{0,1\}^N$ qui à $\omega$ associe le vecteur des réponses de chacun des prisonniers, alors le nombre de survivants est noté $G = \sum_{i=1}^N \mathbb{1}_{F(\omega)_i=\omega_i}$

Pour respecter les contraintes de l'énoncé, la stratégie $F$ s'écrit $F(\omega) = (f_1(\omega_2, \dots, \omega_N), \dots, f_i(\omega_1,\dots,\hat{\omega_i},\dots,\omega_N),\dots, f_N(\omega_1,\dots, \omega_{N-1}))$ avec certaines fonctions $f_1,\dots,f_N : \{0,1\}^{N-1}\to\{0,1\}$.

On suppose à présent que $\omega$ est tiré uniformément parmi $\{0,1\}^N$ (autrement dit le chapeau de chaque prisonnier est tiré à pile ou face équilibré et indépendamment les uns des autres).

Sous ces hypothèses, il est facile de voir que quelque soit la stratégie choisie alors $\mathbb{E}[G]=N/2=n$.

Avec la stratégie décrite dans la première partie alors nous avons $\text{Var}[G]=0$.

Ma question est la suivante : Je me demande quelle serait une stratégie qui maximise cette variance ?
On pourrait penser que la stratégie de répondre au hasard maximise cette variance cependant ce n'est pas le cas :

La stratégie qui consiste à faire en sorte que le prisonnier $2k-1$ dise la couleur du prisonnier $2k$ et que le prisonnier $2k$ dise la couleur du prisonnier $2k-1$ me donne une variance plus importante.

Pourquoi ?

Vu que $\mathbb{E}[G]$ est constante (ne dépend pas de la stratégie) il suffit de maximiser

$$\mathbb{E}[G^2] = \mathbb{E}[G] + 2\sum_{1\leq i < j \leq N}\mathbb{P}(f_i(\omega_1,\dots, \hat{\omega_i},\dots, \omega_N) = \omega_i \text{ et } f_j(\omega_1,\dots, \hat{\omega_j},\dots, \omega_N) = \omega_j)$$.

Si nous avons affaire à une stratégie "répondre au hasard" pour chaque prisonnier, alors chaque terme de la somme double vaut $1/4$. Alors qu'avec la stratégie proposée juste avant, certains termes valent $1/2$ alors que les autres valent $1/4$.

Merci pour avoir lu ce message, la réponse est peut être évidente mais je ne la vois pas. Si vous avez des pistes ou des références en rapport au sujet je suis preneur !

Cordialement

JLapin

Je connais cette énigme mais dans sa version où les prisonniers entendent les réponses des autres.
Elle est présentée de façon très exhaustive ici.
http://cm2.ens.fr/content/des-chapeaux-des-couleurs-et-des-structures-algebriques-1570

Le pdf n'est pas disponible (dommage...) mais encore trouvable grâce au merveilleux site archive.org
https://web.archive.org/web/20070117142812if_/http://www.dma.ens.fr:80/culturemath/maths/pdf/algebre/chapeaux.pdf

PS : désolé, je ne réponds pas au message initial...

Izolg

Merci pour les liens ! Je regarderai ça demain.

Avant d'aller me coucher je pose aussi https://en.wikipedia.org/wiki/Induction_puzzles qui contient une présentation de plusieurs problèmes avec des chapeaux :-)

Izolg

Nevermind, mon insomnie m'a permis de trouver !
La solution est effectivement simple :
Prendre la stratégie qui consiste a supposer pour tous les prisonniers que le nombre total de chapeau blanc est pair (il y a une chance sur deux que ce soit vrai). Ou bien ils sont tous libérés, ou bien ils sont tous pendus. Ainsi avec cette stratégie $\mathbb{E}[G^2] = \frac{N^2}{2}$.

Par ailleurs, pour une stratégie quelconque, alors en majorant trivialement chaque terme de la somme double (à la fin de mon post précédent) par $1/2$. Alors on voit que pour une stratégie quelconque : $\mathbb{E}[G^2] \leq N/2 + N(N-1)/2 = N^2/2$.

On a donc trouvé une stratégie qui maximise cette variance. Après je ne sais pas s'il y a unicité.
Bonne nuit !

Izolg

Bonsoir,

JLapin, j'ai lu le papier que tu as envoyé. Je trouve ça très instructif. Les auteurs n'ont cependant pas l'air de conclure lorsque l'ensemble des prisonniers $I$ est infini, et que l'ensemble des couleurs $\mathcal{C}$ est fini mais pas une puissance d'un nombre premier (et donc n'a pas de structure de corps).

J'ai pensé à la méthode suivante qui permet de contourner le problème :

On suppose $I$ infini et $\mathcal{C}$ ensemble non vide quelconque. J'utilise cependant un résultat du papier qu'a partagé JLapin qui dit qu'on peut munir $\mathcal{C}$ d'une structure de groupe abélien.

Si $u,v$ sont deux élements de $\mathcal{C}^I$ on dit que $u\sim v$ si $\sharp\{i\in I, u_i \neq v_i\}<\infty$, il s'agit d'une relation d'équivalence sur $\mathcal{C}^I$.

Par l'axiome du choix, on choisit un système de représentants $R$ de $\mathcal{C}^I/\sim$ (ie on choisit un élément dans chaque classe d'équivalence) chaque prisonnier aura ce même système de représentants. ($\forall u \in \mathcal{C}^I\text{, }\exists ! v\in R \text{ , }u\sim v$).

Puisque les prisonniers voient tous les chapeaux sauf le leur, alors ils peuvent tous savoir dans quelle classe d'équivalence se trouve la distribution $u\in \mathcal{C}^I$ des chapeaux. Ils trouvent donc le représentant $v\in R \subset \mathcal{C}^I$ tel que $u\sim v$. Aucun prisonnier n'a encore rien dit mais tous on pu "calculer" $v$.

L'un des prisonnier, noté $i_1$, prend la parole et dit la couleur $c_1 := \sum_{i\in I\setminus\{i_1\}}(u_i-v_i)$. Notons que le fait de sommer a un sens car on a supposé $\mathcal{C}$ muni d'une structure de groupe abélienne, et que cette somme existe car elle est en fait finie (puisque $u\sim v$).

À partir de l'information de $c_1$ que les autres prisonniers entendent tous, ils peuvent tous retrouver leur couleur : un prisonnier $i_2$ peut dire $c_2 := c _1- \sum_{i\in I\setminus\{i_1,i_2\}}(u_i-v_i) + v_{i_2} = u_{i_2}$, il trouve ainsi bien sa couleur.

Ainsi tous les prisonniers excepté $i_1$ sont garantis de trouver la couleur de leur chapeau.

A priori je ne vois pas d'arnaque mais on ne sait jamais.

NB : je n'ai utilisé nulle part le fait que $I$ est infini. En fait si $I$ est fini, alors tous les éléments de $\mathcal{C}^I$ sont dans la même classe d'équivalence pour $\sim$. Il n'y a donc qu'un seul représentant dont on peut supposer, sans restriction de généralité, que c'est $(0_\mathcal{C})^I$. La stratégie décrite ci dessus, devient alors la stratégie décrite dans le papier de JLapin pour le cas $I$ fini, $\mathcal{C}$ infini.

Bonne soirée !