Trajectoires 11 : Enigme d'Alexander

GuillaumeAubrun 2017-11-22 10:17:29 UTC #1

N prisonniers ont chacun un chapeau bleu ou rouge. On a tiré au hasard leurs couleurs à l'aide d'une pièce de monnaie non biaisée ; les tirages sont indépendants.

Chaque prisonnier peut voir la couleur de tous les autres chapeaux mais pas du sien. Les prisonniers ne peuvent pas communiquer entre eux.

On interroge successivement chaque prisonnier en lui demandant : "quelle est la couleur de ton chapeau ?". Le prisonnier peut répondre "Bleu", "Rouge", ou bien "Je passe". L'interrogatoire a lieu dans une pièce isolée, les autres prisonniers n'entendent pas la réponse.

A l'issue de tous les interrogatoires, les prisonniers ont la vie sauve si (1) au moins un a répondu une couleur et (2) personne ne s'est trompé. Si jamais les prisonniers ont tous passé, ou bien si un d'entre eux a répondu la mauvaise couleur, ils sont tous exécutés.

Avant qu'on leur distribue leurs chapeaux aléatoires, les prisonniers peuvent se mettre d'accord sur la stratégie à adopter.

Le but de l'énigme est de montrer que les prisonniers ont une stratégie qui leur permet de se sauver avec une probabilité strictement supérieure à 1/2, et même que cette probabilité tend vers 1 quand N tend vers l'infini.

NimpNaw 2017-11-22 13:20:41 UTC #2

Je tente une réponse sans grande conviction :

Avant la distribution, les prisonniers désignent une personne qui répondra bleu si il constate une majorité de chapeau rouge et vice versa.
Tous les autres répondent "je ne sais pas".

Maxdeb 2017-11-22 18:57:45 UTC #3

bonjour

Allez je tente une réponse même si elle pas tout à fait conforme.

La stratégie est la suivante :
Chaque prisonnier utilise son bras droit pour indiquer la parité du nombre de chapeaux rouge qu'il voit : bras levé pour un nombre pair, bras baissé pour un nombre impair. Pareil pour le bras gauche et les chapeaux bleu.

Il regarde ceux qui ont la même position, ils ont le même chapeau.
Et chacun connait la couleur de son chapeau.

Bon, ils ont communiqué entre eux. Donc la solution ne fonctionne pas mais je cherche encore.

Bonne journée à tous.

Maythes 2017-11-22 19:20:15 UTC #4

Ils savent combien ils sont ?

GuillaumeAubrun 2017-11-22 19:27:09 UTC #5

Oui, ils savent combien ils sont !

Pour la proposition de NimpNaw : cela donne aussi une probabilité 1/2, n'est-ce pas ? Puisque les tirages au sort sont indépendants !

Maxdeb 2017-11-22 19:29:10 UTC #6

Je pense que oui car ils arrivent à voir tout les autres chapeaux.

Alors la question est de savoir si ils voient les autres en même temps que les chapeaux mais je pense que non et que ma solution n'est pas valable.

NimpNaw 2017-11-22 19:40:09 UTC #7

Qui décident de qui est le prochain interrogé ?

Maxdeb 2017-11-22 19:48:36 UTC #8

Et savent ils leur rang dans l'interrogatoire?

GuillaumeAubrun 2017-11-22 19:52:40 UTC #9

C'est le grand méchant qui décide de l'ordre des interrogatoires.

Fix 2017-11-22 19:54:58 UTC #10

Alors je tente un truc en live, je vais decouvrir le resultat a la fin de mon post
pour n=3
La strategie est si je vois que du bleu je dis rouge R, si je vois que du rouge je dis bleu B, otherwise je passe P
Les cas possible / Les reponses / Le resultat
RRR / BBB / Dead (1 cas comme ca)
RRB / PPB / Survive (3 cas comme ca pour chaque position de B)
RBB / BPP / Survive (3 cas comme ca pour chaque position de R)
BBB / RRR / Dead (1 cas comme ca)

Donc le taux de survie est de (3+3)/(3+3+2)=6/8=75% de survie

Y a une erreur dans mon raisonnement?
Je continue a voir pour n=4

Maxdeb 2017-11-22 20:02:07 UTC #11

Juste une question encore
Les prisonniers ne connaissent pas l'attribution des chapeaux ?
Ils leur sont présentés avant la distribution et l'interrogatoire. C'est bien cela.

Fix 2017-11-22 20:02:31 UTC #12

Pas besoin d’entorse à la règle !
Chaque prisonnier de numérote et de constitue dans un groupe de 3 note 1,2,..n.

Si un prisonnier repére un groupe k de type RRB ou BBR supérieur à son groupe, il répond passe.
Sinon il répond de la méthode décrit dans mon post plus haut.

Du coup un seul groupe répond vraiment. Et ce groupe est un groupe gagné si il existe.
La proba a d’avoir un tel groupe gagnant est 1-25%^n pour 3n prisonnier !

NimpNaw 2017-11-22 20:18:54 UTC #13

Il me semble que seul les cas où tout le monde à la même couleur sauf un survivrons.

Par contre tout le monde pourrais passer jusqu’à qu'il ne reste que trois personnes et appliquer cette stratégie au 3 personnes ?

GuillaumeAubrun 2017-11-22 21:37:22 UTC #14

En effet Maxdeb, les prisonniers ne connaissent pas l'attribution des chapeaux

GuillaumeAubrun 2017-11-22 21:40:55 UTC #15

Exact pour le 75%, bravo

Tinus 2017-11-23 19:45:27 UTC #16

Si chaque prisonnier compte au début combien il y a d'autre chapeaux rouge et d'autres chapeaux bleu.
Ils suivent ensuite combien de chapeaux de chaque couleur se sont fait interroger.
Si un prisonnier se fait interroger et qu'il reste encore d'autres chapeaux rouge ET d'autres chapeaux bleu non-interrogé, il répond : "ne sait pas".
Si un prisonnier remarque que tout les chapeaux rouge se sont fait interroger, il se précipite à l'interrogatoire et dit qu'il est rouge. (Respectivement pour bleu)
Si des prisonniers voient quelqu'un se précipiter à l'interrogatoire, ils doivent répondre : "ne sait pas" ou la couleur contraire du mec qui s'est précipité.

Je sais que quelqu'un qui se précipite pour se faire interroger, ça fait parti de la communication. Mais c'est un minimum de communication. Et je sens que mon idée peut être amélioré mais je trouve pas comment pour l'instant alors je partage

mikeleyeti 2017-11-27 08:45:30 UTC #17

Bonjour,
Aller je me lance même si je n'ai pas une réponse complète.
Je me suis lancé sur le cas de 8 prisonniers.
J'ai utilisé la rédaction de @Fix
Pour 8 prisonnier le nombre de cas est : 2^8=256 cas possibles
La probabilité d'un de ces cas est C(8,k)/2^8 avec k le nombre de chapeaux bleus et C(n,k) le nombre de combinaisons de k éléments parmi n.

RRRRRRRR  p=1/256
BRRRRRRR  p=8/256
BBRRRRRR  p=28/256
BBBRRRRR  p=56/256
BBBBRRRR  p=70/256
BBBBBRRR  p=56/256
BBBBBBRR  p=28/256
BBBBBBBR  p=8/256
BBBBBBBB  p=1/256

Je pose Nb et Nr le nombre de chapeaux rouges et bleus visibles par une personne.
Dans mon cas on a Nb+Nr=7
Du coup, j'ai élaboré un tableau de réponse suivant le nombre de chapeaux visibles par une personne pour "maximiser" la probabilité de gagner.

Pour 8 prisonniers cela donne : 
    nB  Nr  Réponse du prisonnier
     0   7     B
     1   6     P
     2   5     R
     3   4     B
     4   3     P
     5   2     B
     6   1     P
     7   0     R

Du coup si chaque prisonnier suit ces règles de réponses on obtient :

RRRRRRRR  | BBBBBBBB | PERDU p=1/256
BRRRRRRR  | BPPPPPPP | GAGNE p=8/256
BBRRRRRR  | PPRRRRRR | GAGNE p=28/256
BBBRRRRR  | RRBBBBBB | PERDU p=56/256
BBBBRRRR  | BBBBPPPP | GAGNE p=70/256
BBBBBRRR  | BBBBBBBB | PERDU p=56/256
BBBBBBRR  | BBBBBBPP | GAGNE p=28/256
BBBBBBBR  | PPPPPPPR | GAGNE p=8/256
BBBBBBBB  | RRRRRRRR | PERDU p=1/256

Donc au final , (8+28+70+28+8)/(2^8) = 142/256 soit environ 55,47 % de chance de réussir.
Bon il va falloir que je relise et que je vérifie qu'il n'y a pas d'erreurs. N'hésitez pas à me corriger , je fais ça pendant un devoir surveillé de mes élèves

mikeleyeti 2017-11-27 18:21:44 UTC #18

Suite ... J'ai essayé pour 7 prisonniers :

nB  Nr  Réponse du prisonnier
 0   6     B
 1   5     P
 2   4     B
 3   3     P
 4   2     R
 5   1     P
 6   0     R

Ce qui donne en terme de réponses :

RRRRRRR  | BBBBBBB | PERDU p=1/128
BRRRRRR  | BPPPPPP | GAGNE p=7/128
BBRRRRR  | PPBBBBB | PERDU p=21/128
BBBRRRR  | BBBPPPP | GAGNE p=35/128
BBBBRRR  | PPPPRRR | GAGNE p=35/128
BBBBBRR  | RRRRRPP | PERDU p=21/128
BBBBBBR  | PPPPPPR | GAGNE p=7/128
BBBBBBB  | RRRRRRR | PERDU p=1/128

Ce qui donne : (7+35+35+1)/128 = 78/128 soit environ 60,94 % de chance de gagner.

mikeleyeti 2017-11-30 13:06:22 UTC #19

Bonjour,
J'ai un début de stratégie globable.
Il faut viser le gain des cas centraux . Une fois que c'est fait il faut alterner les réponses P-B-R dans cet ordre vers le haut vers le haut du tableau et P-R-B dans cet ordre vers le bas du tableau. Cela permet de gagner environ 2 cas sur 3. Bon je sais que je ne suis pas clair ... Il va falloir que je mette ça au propre. J'ai testé ma strat pour n=6,7,8 et 9 et ça marche.
A suivre .

sofsoo1995 2017-12-07 03:19:45 UTC #20

Bonjour,

Je tente ma réponse. L'idée de Fix est pas mal. On va adopter la même stratégie. C'est à dire pour k individus, je regarde mes collegue et je réponds P si il y a des couleurs différentes sinon, je réponds B/R. si on a k individu la probabilité de ne pas se tromper et k/(k+1) à condition que au moins un individu voit que des chapeaux B/R. le problème et que si on prend tous les prisonniers notre stratégie ne vas pas marcher car tous le monde va répondre P. On va pour exploiter cette stratégie faire des groupes de prisonnier. On fait par exemple des groupes de k prisonniers. et dans chaque groupe les prisonniers ne regardent que les chapeaux du groupe. dans la plupart des groupes, on aura des groupe perdants. Mais si N augmente la probabilité de tirer un groupe gagnant augmente et tend vers 1.

Un groupe gagnant c'est un groupe ou il est possible de gagner cad un groupe ou un prisonnier donne une réponse.

exemple si on fait des groupe de 10
la probabilité de tirer un groupe potentiellement gagnant est de 11/1024 = 1/100
Et si on a K groupes,
la proba de ne pas tirer de groupe gagnant est de (99/100)^K qui tend vers 0

Donc forcement, on va tirer un groupe gagnant. Le probleme est qu'on risque de tirer trop de groupe gagnant et donc la probabilité va quand même être faible.

Cela fait entorse à la règle mais on peut dire que dès qu'on a un groupe gagnant les autres groupe gagnants répondent comme les groupes perdants.

Si on a N prisonniers, on peut faire N/log(N) groupes de log(N) prisonniers et on pourra vérifier que la probabilité tend vers 1(avec verification que log(N) soit entier).

Propulsé par Discourse, le rendu est meilleur avec le JavaScript activé