Pas de miroir

[Vassillia]

Bonjour à tous, histoire de changer, je propose une petite énigme logique pour se mettre en forme, j'en connais d'autres plus difficiles si vous voulez pour la suite.

Des individus numérotés de 1 à n portent chacun une casquette rouge ou bleue,
Chacun d’eux ignore la couleur de la casquette qu’il porte mais peut voir la couleur des autres casquettes.
Chacun à tour de rôle 1, puis 2, puis 3... puis à nouveau 1, puis 2, puis 3... doit indiquer une couleur.
Quelle stratégie optimale mise au point entre eux avant l'expérience permet aux n individus d’annoncer successivement la couleur respective de sa casquette ?
Qui va parler en dernier dans le pire des cas ?

[GaBuZoMeu]

Bonjour,

Je ne comprends pas bien les règles du jeu. S'il y a plusieurs tours, c'est que les individus ont le droit de se tromper ? Dans ce cas il suffit de deux tours pour que chacun donne une bonne réponse.

[Vassillia]

Les individus ont le droit de se tromper mais aucune personne extérieure ne leur dit s'ils ont raison ou pas.
Le jeu s’arrête quand tous les individus ont successivement donné la bonne réponse, il ne peut pas y avoir d'erreur entre 2 bonnes réponses.
2 tours entiers suffisent, tu as tout à fait raison, il y a une stratégie qui le permet et c'est déjà pas mal je trouve mais peut-on faire mieux que 2 tours entiers ? Je pense que oui et tant qu'à faire, on pourra essayer de démontrer que c'est la stratégie optimale.

[GaBuZoMeu]

D'accord, les n personnes peuvent sans problème donner successivement la bonne couleur de leurs casquettes au deuxième tour, si elles se sont entendues pour donner au premier tour la couleur de celle de la personne suivante dans l'ordre cyclique.
Un argument simpliste pour dire que deux tours sont nécessaires : en un tour il y a 2^n possibilités, juste ce qu'il faut connaître les n couleurs.

[Vassillia]

Ta solution est valable évidemment et c'est celle à laquelle on pense tous intuitivement. Par contre, je ne suis pas convaincue par ta démonstration d'optimalité, les individus sont des individus, ils peuvent raisonner.

Ils s'entendent pour que le premier dise "rouge" si il voit un nombre pair de casquette rouge et "bleue" si il voit un nombre impair de casquette rouge.
Tous les individus suivants peuvent "calculer" leur couleur de casquette en regardant les autres et ne se tromperont pas. Si la parité du nombre de casquettes rouges en omettant celle du premier est bien la même que celle annoncée alors il a une casquette bleue sinon il a une casquette rouge.
A la fin du tour, si le jeu ne s'est pas arrêté le premier individu donne l'autre couleur et cette fois il a forcément raison. On a donc 50% de chances de finir en exactement 1 tour et 50% de chances de finir en 1 tour + 1 individu.

Est-ce que c'est optimal ? Je pense vraiment que oui car le premier individu qui parle ne peut pas encore avoir eu d'indication sur la couleur de sa casquette donc il a forcément 50% de chances de se tromper.
C'est un peu fourbe comme stratégie mais j'aime beaucoup.

[GaBuZoMeu]

Oui, ce qui ne va pas dans mon argument simpliste est que chaque personne a déjà l'information sur n-1 casquettes ; il ne lui manque donc plus qu'une information, qui peut être donnée par la première personne aux n-1 suivants. L'astuce de parité est très jolie.

[MMu]

Astucieux en effet. On peut généraliser ..

[Vassillia]

N'hésite pas à proposer des variantes si tu as des idées de généralisation

[MMu]

Notons les couleurs avec .
Le voit chapeaux de la couleur et indique alors la "couleur" .
Par le même procédé ceux qui ont la "couleur" obtiennent (en évitant le ) : .
And so on ...