Mon coup de coeur du jour - Page 1

C'est une petite énigme pour les gens qui s'ennuient.

On a une infinité de gens portant des chapeaux. Chaque chapeau est soit rouge, soit bleu. Chaque personne peut voir la couleur du chapeau des autres, mais pas du sien. Et il est interdit de parler de la couleur du chapeau des autres.

On demande à chacun de deviner la couleur de son propre chapeau, et sur la totalité des gens on n'autorise qu'un nombre fini d'erreurs (sinon, ils seront tous condamnés à mort!). Ils doivent tous répondre simultanément.

Cependant, on les autorise en préliminaire à se concerter pour décider d'une stratégie.


Comment peuvent-ils faire pour passer l'épreuve? (naturellement ils sont tous super-intelligents)

ben ils trouvent un code secret pour dire la couleur du chapeau sans en parler explicitement (ha ha, t'avais qu'à mieux la traduire )

S'il essaient de tricher on les tue tous !

qu'est ce qui te gène dans la formulation ?

Je reformule si tu veux :

* Le jour 1 ils n'ont pas de chapeau, et ils font un meeting où ils discutent de la solution à apporter.
* Le jour 2 on leur met chacun un chapeau sur la tête, ils ne peuvent voir que celui des autres et ils doivent tous répondre en même temps sans causer.

voilà, sans communication et pas juste sans dire à qqun la couleur de son chapeau ^^

./3 > Ils ne s'échangent aucun signe et aucun mot ? (Edit: cross)

aucun signe et aucun mot, ils peuvent seulement regarder les chapeaux des autres !

J'y réfléchis et je te donne ma réponse après la gym

ben c'est simple : quelqu'un sépare toutes les personnes en 2 groupe, mais sans parler, en fonction de la couleur des chapeaux.

les mec comprennent en regardant les gens autour d'eux quel couleur est leur propre chapeau => aucun ne se trompe, à part la personne qui a séparé les 2 groupes.

[edit] zut cross.... ! pas vu les posts apres le ./3

Séparer selon la couleur des chapeaux, c'est pareil que parler de la couleur des chapeau => on coupe la tête au mec !

./8 > c'était exactement ce que je voulais dire avant qu'Hippo nous précise que tout signe était interdit (séparer = faire un signe)

bon, je pense que j'ai une solution :*

chaque personne se met en couple.

et chaque personne de chaque couple doit dire la couleur inverse du chapeau de son partenaire.

vu qu'ils ont chaqu'un 50% de chance d'avoir un chapeau rouge et 50% de chance d'avoir un chapeau bleu, l'erreur sera moindre

on pourrait faire egalement par groupe de 4 :

si 0xRouge et 3xBleu => dire rouge
si 1xRouge et 2xBleu => dire rouge
si 2xRouge et 1xBleu => dire bleu
si 3xRouge et 0xBleu => dire bleu

./11 > Ca reste un nombre infini d'erreurs

bon, dans ce cas la, ca veut dire qu'il ne peut y avoir qu'une erreur... car si il y a plus d'une erreur, vu que le nombre est infini, il y a forcement une infinité d'erreur...

donc il faut bien une sorte d'arbitre qui se sacrifie pour le groupe... vrai ou faux ?

Hmm, je ne crois pas que la solution des couples fasse faire moins d'erreurs. Mais peut être qu'en creusant de ce côté là, on arrive effectivement à augmenter la probabilité de réussite.

mais attention, dans le problème on demande un nombre fini d'erreurs

(bicross)

12> En fait, je ne crois pas qu'il soit possible de descendre à UNE erreur. Un nombre fini d'erreur me parait le minimum possible.

./13 > Ben non s'il y a 2 erreurs c'est fini aussi.

Hippopotame (./3) :
* Le jour 2 on leur met chacun un chapeau sur la tête, ils ne peuvent voir que celui des autres et ils doivent tous répondre en même temps sans causer.

ben si ils parlent tous en meme temps, ca va être incompréhensible, non ?

./16 > Donc s'ils disent tous "blouge" en même temps, c'est bon

Je te rejoins dehors.

ben na, faut dire violet !


je re-sors....

./15> et puis rien n'interdit aux G.O. de mettre des chapeaux rouges à tout le monde, non ?



alors (pour les matheux) comme dit dans le forum jeux, il n'y a pas de solution mesurable : sinon l'événement "la ième personne se trompe" est bien défini et a une probabilité 1/2, donc presque sûrement il y a une infinité de personnes qui se trompent... donc concrètement ça implique que par exemple au moins une personne dépend d'un nombre non borné de chapeaux, et donc que les trucs à la Spipu qui ne dépendent que de quelques voisins ne peuvent pas marcher ; ça veut dire aussi que c'est complètement théorique comme problème, parce que rien ne dit que le "jour 2" ne va pas prendre 3 millénaires, et donc que tout le monde sera mort largement avant d'être exécuté ou libéré

question à hippo : est-ce que ta stratégie s'exécute au moins en un temps fini ? (avec des yeux capables de voir juste un nb fini de chapeaux en un tps fini )

Ils se mettent par couple, puis chaque personne du couple, regarde le chapeau de l'autre, et troque son chapeau avec son binôme. Ils ont donc sur leur tête le chapeau qui était avant à l'autre, mais qui est maintenant le leur, ils donne la bonne couleur ainsi.

je "pense" que c'est compté comme un signe/geste

Mais non, c'est du commerce !

Pollux (./19) :
alors (pour les matheux) comme dit dans le forum jeux, il n'y a pas de solution mesurable : sinon l'événement "la ième personne se trompe" est bien défini et a une probabilité 1/2, donc presque sûrement il y a une infinité de personnes qui se trompent...

Exact.
Ca devrait te mettre sur la piste.

Et c'est clair que c'est violent à expliquer non mathématiquement

ça veut dire aussi que c'est complètement théorique comme problème,

Tout à fait.
Mais en même temps, une infinité de personnes, c'est complètement théorique comme énoncé

parce que rien ne dit que le "jour 2" ne va pas prendre 3 millénaires,

Ils ont intérêt à parler vachement vite.

question à hippo : est-ce que ta stratégie s'exécute au moins en un temps fini ? (avec des yeux capables de voir juste un nb fini de chapeaux en un tps fini )

Définis "temps fini" précisément.

S'ils voient en temps fini tous les autres chapeaux (et donc traitent cette information en temps fini), alors pouf la solution est instantanée, en O(1).

Un individu peut-il savoir s'il a eu raison ou non, individuellement ?

./25 > Qu'importe vu qu'ils répondent tous en même temps :-/

Au moment où il exécute la stratégie, non, il ne peut pas savoir s'il est sûr d'avoir raison ou sûr d'avoir tort.

blackGhost (./26) :
./25 > Qu'importe vu qu'ils répondent tous en même temps :-/

Mais ils peuvent recommencer un nombre fini de fois.

hippo : ok

nan nan, un seul essai.

ah, j'ai mal compris « faire un nombre fini d'erreurs. »