Salut,

Si tu fouilles le forum, tu verras que cette énigme y est déjà postée.
D'ailleurs, on peut la généraliser avec autant de couleurs que l'on veut.

Cela dit, c'est l'une des plus belles énigmes de logique que je connaisse...
Klim.

Comme disait kosmo le banni, c'est pas faux

Euh...
Tu crois qu'un nain voit mieux les chapeaux des 99 nains devant lui, qu'un géant verrait les chapeaux des 99 géants devant lui ?

Peut-être un nain posteur, sûrement un nain croyable !

Mmmmhhhh !
Et toi une naine orme amie ! ❤❤❤

Vous êtes d'incorrigibles moqueurs et je ne me mets pas à l'écart
Pourquoi des nains en effet !

J'ai retrouvé sur le forum la réponse donnée à l'époque.
Pour N joueurs (nains) et n couleurs, la stratégie semblait imparable pour les (N-n) derniers joueurs (nains) et Bayes-sophistiquée pour les n premiers.

Cette logique de modulo était-elle sans faille?
Si oui, comme l'a dit Klim, c'était la grande classe.

Bonjour,
Je suis d'accord avec Klimrod #13, mais je mettrais plutôt [latex]n^J ≥ 2^{(n-1)}[/latex] (utile notamment pour n=2).

Personnellement, je ne suis pas d'accord.

Le premier joueur a 1 chance sur le nombre de couleurs de gagner.
Dans le doute, il l'utilise avec la stratégie "modulo", ce qui ne change pas grand chose pour lui.

Pour n couleurs, il annonce donc leur somme modulo n avec une valeur de 0 à (n-1) attribuée à chaque couleur.

Tous les joueurs suivants connaissent donc la somme des n-1 derniers chapeaux modulo n énoncée par le premier joueur.

Ils connaissent aussi tous la somme de ces chapeaux hormis le leur , et donc aucun n'a de doute pour dire la couleur de son chapeau.

Effectivement, on peut difficilement faire mieux que gwen27.

Ca finit par devenir prenant ce truc

Sur tableur avec dix couleurs et plus de 100 joueurs tirés au hasard, j'en suis arrivé aux mêmes conclusions que Gwen.

On attribue les nombres 0 à (n-1) aux couleurs dans un ordre identique pour chaque joueur.
Chacun des joueurs calcule modulo n la somme des couleurs qu'il voit devant lui en leur donnant la valeur b, chacun retenant cette valeur à son rang.

Le premier prononce le modulo qu'il a obtenu et a une chance sur n de gagner.
Il ne sait rien le concernant mais renseigne tous les autres.
A ce stade de la conversation...

Tous les suivants par récurrence énoncent
(a-b) modulo  n
avec :
   le résultat entendu du joueur précédent: a
   leur résultat calculé: b

Spoiler : [Afficher le message] Comme le dirait Stanraf, il suffira d'un signe pour qu'on se vrille totalement

Un calcul, une information; ils sont tous sauvés à partir du deuxième.
Pas trop cher en calcul et
(N-1) + (1/n) sauvés.
Pas mal!

Si je me suis pas trompé dans le suivi de ce post, quelques questions me viennent:

1. Si le nombre initial par couleur est connu à l'avance, il me semble qu'on peut répondre à coup sûr pour tout le monde.

2. Je ne suis ni féru de crypto ni d'algorithmes, chacun de ceux qui me connaissent le savent.
Mais toujours heureux d'apprendre, je lis et expérimente.
En novice (un peu éclairé), je suis impressionné par l'économie de calcul de la méthode (borne initiale fixée ou non).
Aux rois de l'algorithmique de nous prouver la vertu de la file indienne.

3. Notre ami Machiavelli a posté en disant avoir eu cette énigme en entretien.
Mais où diable était-il candidat au point de réunir une master-class de P2t ?
Avec des nains en plus

Salut à tous,
Je ne suis pas trop d'accord avec gwen27 car la règle dit que: "Si qui que ce soit dit quoi que ce soit d'autre que "rouge", "blanc", ou "vert", tous les nains sont exécutés. "
Donc la seule solution que je vois est que le dernier nain de la file se sacrifie en citant à la suite la couleur de chaque chapeau du premier au 99eme.
Et tous connaitront la couleur de leur chapeau sans contrevenir aux règles.

Et si chaque nain annonce simplement la couleur du chapeau de celui qui se trouve devant lui, c'est pas plus simple ?
Le dernier de la file devra évidemment dire une couleur au bol quand on lui demandera celle de son couvre chef: cela ne change rien par rapport à vos méthodes plus compliquées!