Forum de mathématiques - Bibm@th.net

Glozi

Invité

Des énigmes avec des chapeaux

Bonjour, voici une série de petites énigmes (variantes de la même énigme), les premières sont connues les dernières le sont moins.

Énigme originale :
Il y a $N\geq 2$ prisonniers dans une pièce. Chaque prisonnier reçoit sur sa tête un chapeau, noir ou blanc, qui est placé sans qu'il le voit par un juge impartial. Les prisonniers voient les chapeaux des autres mais pas leur propre chapeau. À tour de rôle on leur demande de deviner la couleur de leur chapeau (noir ou blanc). Si un prisonnier répond juste il est libéré sinon pendu. Certains prisonniers peuvent, s'ils le souhaitent, répondre simultanément. Les prisonniers entendent les réponses des prisonniers précédents. À part pour donner leur réponse, les prisonniers ne peuvent évidemment pas communiquer entre eux.

Cependant les prisonniers étaient au courant de cette "expérience" et ont donc pu établir une stratégie commune avant qu'on les mette dans cette pièce.

Question : Quelle serait une stratégie qui minimise le nombre $V$ (pour victime(s)) de prisonnier(s) qui ne s'en sortirons pas dans le pire des cas (pire distribution initiale des chapeaux pour la stratégie choisie) ?

Exemple :
Dans la stratégie "on répond chacun au hasard indépendamment les uns des autres" alors ce nombre $V$ vaut $N$ car dans le pire des cas, aucun prisonnier ne s'en sort.

▼Un autre exemple qui n'est pas la solution

Dans la stratégie "le prisonnier $2k-1$ dit la couleur du chapeau du prisonnier $2k$ et le prisonnier $2k$ dit la couleur que vient de dire le prisonnier $2k-1$ alors $S=N/2$ (si $N$ est pair). Car tous les prisonniers $2k$ vont s'en sortir à coup sur, mais les autres on ne sait pas, et dans le pire des cas tous les prisonniers $2k-1$ sont pendus.
Il est possible de faire mieux que ça... comment ?

▼Indice

Il est possible de trouver une stratégie avec $V=1$ (au pire un seul prisonnier est pendu) ! Mais laquelle ?

▼Gros indice

Il y a ou bien un nombre pair de chapeaux blancs, ou bien un nombre impair de chapeaux blancs

Variante 1 :
On suppose que les prisonniers n'entendent pas les réponses des autres prisonniers (et ils ne savent pas non plus si les autres prisonniers sont pendus ou libérés).
Même question.

Variante 2 :
Dans le contexte de l'énigme originale, on suppose que les chapeaux peuvent être tirés parmi $n$ couleurs différentes (pas forcément $n=2$).
Même question.

Variante 3 :
Dans le contexte de l'énigme 1, on suppose que les chapeaux ont leur couleur qui est choisie dans un ensemble possiblement infini (peut être non dénombrable).
Même question.

Variante 4 :
Dans le contexte de l'énigme 1, on suppose maintenant que l'ensemble des prisonniers $I$ est infini (dénombrable si vous voulez mais pas nécessairement), et que l'ensemble des couleurs est quelconque (fini ou possiblement infini aussi).
Même question.

Variante 5 :
Dans le contexte de la variante 1, avec un ensemble infini de prisonniers et un ensemble infini pour le choix des couleurs.
Trouver une stratégie qui fait que dans tous les cas il n'y a qu'un nombre fini de prisonniers qui seront pendus.

▼Indice/solution partielle

À l'origine je m'intéressais surtout aux variantes 1 et 5 du problème, mais on m'a conseillé de lire https://web.archive.org/web/20070117142 … apeaux.pdf ce papier répond aux variantes $2,3,4$, bien que la $4$ n'est pas complètement traitée il me semble.

SI vous connaissez déjà une solution à l'énigme originale vous pouvez vous lancer dans les variantes, mais avant de vous lancer dans les variantes je vous conseille de résoudre l'énigme originale.

Attention, pour les variantes $3$ et $4$ et $5$ quelques notions en algèbre générale sont conseillées (et peut être aussi l'utilisation de l'axiome du choix)...

Bonne chance :-)

Boody

Membre

Inscription : 31-03-2014

Messages : 183

Re : Des énigmes avec des chapeaux

...

Énigme originale :
Il y a $N\geq 2$ prisonniers dans une pièce. Chaque prisonnier reçoit sur sa tête un chapeau, noir ou blanc, qui est placé sans qu'il le voit par un juge impartial. Les prisonniers voient les chapeaux des autres mais pas leur propre chapeau. À tour de rôle on leur demande de deviner la couleur de leur chapeau (noir ou blanc). Si un prisonnier répond juste il est libéré sinon pendu. Certains prisonniers peuvent, s'ils le souhaitent, répondre simultanément. Les prisonniers entendent les réponses des prisonniers précédents. À part pour donner leur réponse, les prisonniers ne peuvent évidemment pas communiquer entre eux.
...

Bonjour Forum,

▼V = ...

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.

...
Variante 1 :
On suppose que les prisonniers n'entendent pas les réponses des autres prisonniers (et ils ne savent pas non plus si les autres prisonniers sont pendus ou libérés).
Même question.

Est-ce qu'on sait quand même quels prisonniers répondent (même si on n'entend pas leur réponses et qu'on ne sait pas ce qui leur arrivent) ?

Dernière modification par Boody (03-11-2022 01:53:54)

Glozi

Invité

Re : Des énigmes avec des chapeaux

Bonjour,
@Boody
Bien joué pour la première enigme :-)
Pour ta question, dans ma tête les prisonniers répondent tous "simultanément" mais je suis curieux de savoir à quoi tu penses ? Mais si tu veux, les prisonniers ont des maillot numérotés de 1 a N. Puis le bourreau les interroge un par un dans cet ordre dans une pièce annexe.

▼petit indice

en revanche dans la stratégie qu'ils vont élaborer, ils peuvent se mettre d'accord sur qui va appliquer telle stratégie personnelle...

Bonne journée

Glozi

Invité

Re : Des énigmes avec des chapeaux

Bonjour,
Je me rends compte que j'avais complètement oublié ce post.
Je mets ici les solutions des énigmes.

▼solution énigme originale

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).

▼solution variante 1

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).

▼solution variante 2

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$.

Pour les variantes 3, 4 et 5 nous aurons besoin du lemme suivant (voir https://web.archive.org/web/20070117142 … apeaux.pdf c'est là où je l'ai trouvé)

▼lemme

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).

▼solution variante 3

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$.

▼solution variante 4

$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 !

▼solution variante 5

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.

J'ai rédigé ça à la va-vite, j'espère qu'il n'y a pas trop d'erreurs !

Bonne journée