Problème des chapeaux (facile)

[invitebd020be0]

On prévient les prisonniers d'une prison qu'on va leur attribuer à chacun (au hasard) soit un chapeau blanc soit un chapeau noir. On leur dit aussi qu'on les mettra en ligne devant la porte de sortie et qu'on les questionnera chacun leur tour (en partant du dernier pour arriver jusqu'au premier) : si le prisonnier interrogé donne la couleur de son chapeau (qu'il ne voit pas bien entendu) on le libère.
Chaque prisonnier voit tous les chapeaux devant lui mais ne voit pas le sien.

=> On leur laisse du temps pour mettre au point une stratégie.

=> Quelle est la stratégie à employer pour faire sortir le maximum de prisonniers ?
-----

[invite427a2582]

Le dernier compte le nombre total de chapeaux blancs et de chapeaux noirs et le dit au voisin qui fait de même et pourra ainsi déduire la couleur de son chapeau.
On sauve ainsi 99 prisonniers, le dernier a une chance sur 3 de survivre ^^

[piwi]

J'ai quelque chose de simpliste mais bon c'est une première approche.
Le premier donne la couleur du chapeau de devant. Il y a 1/2 chances que ça soit aussi la sienne.
Le gars de devant donne la couleur de chapeau qu'il a entendu donc lui il a 100% de chances de sortir.
On reprend le cycle devant.
Du coup on a 50% des personnes qui sont certaines de sortir et 50% des personnes qui ont 1/2 chances de sortir.
Y a 75% des prisonniers qui sortent normalement.

Bon c'est sommaire, on peut peut être faire mieux.
Cordialement,
piwi

[invite8ef897e4]

Bonjour,

il existe une strategie qui permet de liberer de facon certaines tous les prisonniers sauf 1.

 Cliquez pour afficher

attribue 1 a noir et 0 a blanc, le premier prisonnier qui parle annonce la parite de la somme de tout ce que portent les autres. Munis de cette information, le prisonnier suivant peut en deduire la couleur de son propre chapeau, et caetera pour tous les autres. Le premier se sacrifie en quelque sorte, il ne s'en sort que si la somme de tous les chapeaux (y compris le sien !) est paire

[A voir en vidéo sur Futura]

[piwi]

Oui bon mais je ne pense pas que les regles autorisent à dire autre chose qu'une couleur sinon effectivement l'info remonte facilement.

[invitebd020be0]

On ne peut pas dire autre chose que "blanc" ou "noir"...
Pas d'indice de sonorité ou de mouvements, juste l'information blanc ou noir...
EDIT : Ta réponse n'est pas très très claire, humanino...je vois l'idée (puisque je connais la solution) mais je pense que pour ceux qui veulent la solution, il sera difficile pour eux de te comprendre

N'oubliez pas qu'ils ont le droit de se réunir avant pour mettre une stratégie en place.

[invite8ef897e4]

Ouais je suis jamais clair de toute facon, c'est pas grave
Si quelqu'un veut prendre le temps d'expliquer en longueur...

[invitea7fcfc37]

Ouais je suis jamais clair de toute facon, c'est pas grave
Si quelqu'un veut prendre le temps d'expliquer en longueur...

Moi j't'ai trouvé assez clair
Ils se réunissent avant et se disent que avoir un chapeau blanc correspond à 0 et un chapeau noir à 1.
Le premier qui doit parler regarde les chapeaux des autres.
Il compte le nombre de chapeaux blancs, il y en a B, et le nombre de chapeaux noirs, il y en a N.
En tout il y a B+N+1 chapeaux.
Il doit donner un renseignement qui renseigne sur la parité de N.
Si N est pair, il annonce Noir, si N est impair il annonce Blanc.
Bon lui son sort est déterminé par le hasard

Maintenant n'importe quelle autre personne connaît sa couleur.
Elle compte le nombre de chapeaux noirs et de chapeaux blancs qu'elle voit sauf celui du premier à avoir parler.

• si le premier annonce Noir, il y a donc un nombre pair de chapeaux noirs, donc si la personne voit un nombre impair de chapeaux sans compter celui du premier à avoir parlé, elle a donc un chapeau noir. Si elle voit un nombre pair de chapeaux noirs, elle a un chapeau blanc.
• si le premier annonce Blanc, il y a donc un nombre impair de chapeaux noirs, donc si la personne voit un nombre pair de chapeaux sans compter celui du premier à avoir parlé, elle a donc un chapeau noir. Si elle voit un nombre impair de chapeaux noirs, elle a un chapeau blanc.

[piwi]

Moi j'ai une amélioration de ma méthode:
On considère les personnes par 4.
Le premier donne la couleur dominante des trois autres devant. Il a lui même toujours 1/2 de sortir.
Les trois autres. Si le premier voit les deux chapeaux devant lui de la couleur dominante il a tout intérêt à énoncer la couleur opposée. En effet il n'y a que 1/8 chances que tous les chapeaux soient de la même couleur. Il a donc 7/8 de sortir. S'il voit les deux couleurs devant lui il sait qu'il a la couleur dominante, il sort à tous les coups.
Le second retire une info du devenir du premier il sort à tous les coups. Le dernier sort aussi à tous les coups.
On a donc
1/4+1/4+1/4x7/8+1/4x1/2. Ca donne à peu près 84% de chances de sortir.

Je ne sais pas si l'on peut faire mieux avec cette méthode car il me semble que donner la couleur dominante de 5 chapeaux donne trop d'incertitude et ne permet aux personnes de décider autrement qu'au hasard. Je peux me tromper, c'est une intuition.

EDIT: bon ben manifestement il y avait une meilleure méthode
Cordialement,
piwi

[piwi]

Remarquez que la méthode optimale suppose un nombre raisonnable de prisonniers pour que le dernier puisse les compter dans la file. Si il y a 1000 prisonniers à la queue leuleu c'est pas gagné.
Alors que ma méthode est possible même si l'on a une infinité de prisonniers vu qu'elle ne repose pas sur un seul compteur mais sur des sous groupes

Bon ok je vends ma soupe là

[piwi]

re edit.
J'ai été un peu optimiste sur la proba conditionnelle...
En fait ca ne marche pas mon truc. Il a une chance sur deux d'avoir un chapeau de la couleur dominante, point barre.

En fait mon truc est tout pourri. Oubliez le!

Cordialement,
piwi

[invite970ffd48]

Ils doivent s'aligné devant l'entré un après l'autre tjrs par le centre, j'explique

N = Noir B = Blanc | = porte


le premier se place près de la porte
le second derière le premier

et le troisième est important si on a : N N| ou B B| il se place derrière les deux si on a N B il se place entre les deux donc on aura N N B ou N B B et on continue ainsi jusqu'à 100, tant qu'il n'y a qu'une couleur le prochain le place en dernier.

au final on aura donc ... N N N N B B B B B B ...| chaque fois qu'un prisonnier vient se palcer il permet au précédent de connaître la couleur selon que le prisonnier se palce devant ou derrière ( le plaçant avec les noir ou avec les blanc )

puis celui de devant revient au centre ( il sait déjà la couleur de sont chapeau du coup il permet au dernier de connaître sa couleur

ceci permet de sauvé 100 % des prisonnier !!!

Merci et Bonne fin de semaine !!

oh et en passant ! il me semble improbable que tout les prisonniers soit de parfait logiciens alors cette méthode est idéale car elle pourrait être faite par des enfants !

[piwi]

Oui mais avec ta méthode ils s'organisent eux même ce qui signifie que tout le monde sait quel chapeau il a sur la tête avant de s'organiser
Effectivement dans ce cas autant les libérer tous tout de suite!

piwi

[invitea7fcfc37]

Oula j'sais pas pourquoi j'avais pas lu l'énoncé j'étais persuadé que chacun voyait tous les autres chapeaux. Il faut donc apporter une variante dans mon explication de la méthode de humanino : il faut que chacun mémorise la parité des chapeaux noirs qui étaient avant lui, c'est un peu plus dur

Sinon cadors, je doute que les prisonniers se placent comme ils veulent

[invitebd020be0]

La réponse était effectivement celle sur la parité !
Pour info, combien de temps as tu mis pour la trouver ?
Moi j'ai mis 20 minutes (mais en prenant mon gouter en même temps )...
Posez le à des non-mathématiciens et vous seriez surpris de voir que personne n'est capable de le resoudre alors qu'une fois la solution connue ce problème semble si simple ! ^^
Bonne soirée

[invite8ef897e4]

Pour info, combien de temps as tu mis pour la trouver ?

Je connaissais deja, pas exactement sous cette forme, mais la premiere fois qu'on me l'a pose j'ai du mettre 4 ou 5 minutes, pas tres longtemps. Mais bon, j'ai la prepa math loin derriere moi ca aide
on rajeunie pas...

[invite970ffd48]

Oui mais avec ta méthode ils s'organisent eux même ce qui signifie que tout le monde sait quel chapeau il a sur la tête avant de s'organiser
Effectivement dans ce cas autant les libérer tous tout de suite!

piwi

Non ! selon ma méthode ils ne connaisse pas la couleur de leur chapeau avant de s'organisé, il ne font que se placé chacun leur tour entre deux personne dont la couleur est différente du coup, il finisse par séparer les blancs des noirs et c'est cela qui leur permet de connaître la couleur de leur chapeau

L'énigme dit :

=> On leur laisse du temps pour mettre au point une stratégie

cela n'indique pas une limite de temps précise et une limite dans les stratégie utilisables, alors je crois qu'ils doivent utilisé cette stratégie ou alors s'aligner de la même manière le long d'un mur (comme dans la variante de cette énigme) afin de connaître leur couleur avant d'être placé en file, dans tout les cas je suis convaincu que 100% des prisonnier peuvent être sauvés !