|
#1 - 27-05-2016 19:38:45
- Machiavelli
- Amateur de Prise2Tete
- Enigmes résolues : 12
- Messages : 1
nains et vhapeaux
Bonjour, une petite énigme que l'on m'a faite lors d'un entretien.
100 nains sont dans une pièce. On leur annonce qu'ils seront convoqués chacun leur tour hors de la pièce, qu'un chapeau sera mis sur leur tête, et qu'il sera vert, blanc ou rouge. Ils ne verront pas leur propre chapeau. Une fois le chapeau placé sur leur tête, ils iront se ranger en fil indienne. On suppose que chaque nain a la capacité de voir la couleur de tous les chapeaux devant lui. Si un nain se retourne, ou tente de discerner la couleur de son chapeau, tous les nains sont exécutés.
Le jeu est le suivant: on annonce aux nains qu'une fois que tous auront reçu un chapeau, ils devront chacun leur tour et dans un ordre qu'ils détermineront eux même, dire une couleur. Si un nain devine la couleur de son chapeau, il est relâché, autrement il est exécuté. Si qui que ce soit dit quoi que ce soit d'autre que "rouge", "blanc", ou "vert", tous les nains sont exécutés. On octroie aux nains un moment de réflexion dans la pièce pour déterminer la stratégie minimisant le nombre de perte.
Quelle est cette stratégie?
#2 - 27-05-2016 20:09:31
- Klimrod
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 4050
- Lieu: hébesphénorotonde triangulaire
Nains et chapeax
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.
J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.
#3 - 29-05-2016 20:32:03
- NickoGecko
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1821
Naiins et chapeaux
Pourquoi des nains ?
Il aurait pu pleuvoir, con comme il est ! (Coluche)
#4 - 29-05-2016 21:45:39
- papiauche
- Sa Sainteté
- Enigmes résolues : 49
- Messages : 2131
Nains et chpeaux
Comme disait kosmo le banni, c'est pas faux
"Je ne lis jamais un livre dont je dois faire la critique. On se laisse tellement influencer." O. Wilde
#5 - 30-05-2016 15:04:09
- PRINCELEROI
- Elite de Prise2Tete
- Enigmes résolues : 33
- Messages : 1274
nainq et chapeaux
Parce qu'il est plus facile de voir la couleur d'un chapeau quand il est porté par un nain! Ben quoi! c'est pas vrai?
#6 - 30-05-2016 15:10:14
- Klimrod
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 4050
- Lieu: hébesphénorotonde triangulaire
Nins et chapeaux
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 ?
J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.
#7 - 30-05-2016 20:22:11
- shadock
- Elite de Prise2Tete
- Enigmes résolues : 39
- Messages : 3334
nains et chapezux
J'en déduis que Klim est nain
"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline
#8 - 30-05-2016 20:33:20
- Klimrod
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 4050
- Lieu: hébesphénorotonde triangulaire
naind et chapeaux
Peut-être un nain posteur, sûrement un nain croyable !
J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.
#9 - 30-05-2016 20:48:02
- fvallee27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1264
aNins et chapeaux
Un naindéfectible ami, pour moi.
Science sans conscience n'est que scie à saucisses
#10 - 30-05-2016 21:00:00
- Klimrod
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 4050
- Lieu: hébesphénorotonde triangulaire
Nain set chapeaux
Mmmmhhhh ! Et toi une naine orme amie ! ❤❤❤
J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.
#11 - 30-05-2016 22:57:30
- dhrm77
- L'exilé
- Enigmes résolues : 49
- Messages : 3004
- Lieu: Fanning Island-?-Lac Tele,Mali
Nains ett chapeaux
Concernant la stratégie, s'il y a un nain bécile dans la groupe il faut le placer de manière a ce qu'il parle en dernier... pour limiter les pertes.
Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt
#12 - 30-05-2016 23:41:39
- papiauche
- Sa Sainteté
- Enigmes résolues : 49
- Messages : 2131
Nains t chapeaux
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.
"Je ne lis jamais un livre dont je dois faire la critique. On se laisse tellement influencer." O. Wilde
#13 - 30-05-2016 23:52:31
- Klimrod
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 4050
- Lieu: hébesphénorotonde triangulaire
Nains et chapeaaux
Je ne crois pas ! Sauf erreur de ma part, la stratégie est imparable pour TOUS les joueurs sauf le premier qui parle (qui est donc le dernier de la file).
Ah non, tu as raison, c'est un peu plus compliqué...
Pour n couleurs, on a besoin de n-1 bits pour coder les n-1 parités de n-1 couleurs (la parité de la dernière couleur se déduit de la somme des parités des autres couleurs). Le(s) premier(s) joueur(s) qui parle(nt) doi(ven)t donc être capable(s) de décrire 2^(n-1) possibilités.
Pour n = 2 couleurs, seul le 1er joueur est dans l'incertitude, les suivants jouent à coup sûr. Pour n=3, n=4, n=5 ou n=6, seuls les 2 premiers joueurs sont l'incertitude. Pour n=7 jusqu'à n=10, seuls les 3 premiers joueurs sont dans l'incertitude.
Si J est le nombre de joueurs dans l'incertitude, alors J est le plus petit entier tel que : n^J > 2^(n-1)
Je me trompe ?
J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.
#14 - 31-05-2016 07:18:34
- enigmatus
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
ains et chapeaux
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).
#15 - 31-05-2016 07:57:19
- Klimrod
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 4050
- Lieu: hébesphénorotonde triangulaire
Nains te chapeaux
Ah oui ! Evidemment !
J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.
#16 - 31-05-2016 17:22:03
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,969E+3
nainq et chapeaux
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.
#17 - 31-05-2016 18:16:44
- Klimrod
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 4050
- Lieu: hébesphénorotonde triangulaire
aNins et chapeaux
Merci Gwen !
Je savais bien que la stratégie était imparable pour TOUS les joueurs sauf le premier qui parle (qui est donc le dernier de la file), mais je ne me rappelais plus comment...
J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.
#18 - 31-05-2016 18:30:29
- enigmatus
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
Nains et hapeaux
Effectivement, on peut difficilement faire mieux que gwen27.
#19 - 31-05-2016 18:58:54
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,969E+3
nains zt chapeaux
La différence entre les joueurs à partir du second est juste que certains chapeaux sont vus et d'autres "entendus" en fonction des joueurs précédents. Mais leurs cas sont équivalents : connaissant deux sommes modulo n , on connait leur différence à coup sûr si elle est comprise entre 0 et n-1.
#20 - 31-05-2016 22:34:55
- papiauche
- Sa Sainteté
- Enigmes résolues : 49
- Messages : 2131
nains er chapeaux
"Je ne lis jamais un livre dont je dois faire la critique. On se laisse tellement influencer." O. Wilde
#21 - 01-06-2016 14:47:00
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,969E+3
nains et chzpeaux
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
Je dirais plutôt : (b - a) modulo n Ou b est le résultat donné par le premier joueur et a et la somme des chapeaux vu par le joueur + celle de tous les chapeaux énoncés par les joueurs précédents.
Aux rois de l'algorithmique de nous prouver la vertu de la file indienne.
Pas d'autre intéret que de commencer par celui qui voit tout le monde, puis le suivant... S'ils étaient en rond et se voyaient tous, il suffirait que l'un d'entre eux ait l'esprit de sacrifice, énonce la somme modulo n de ce qu'il voit et avec cette seule information, tous les autres pourraient répondre simultanément sans même attendre la réponse du voisin. Le moins doué peut se permettre d'attendre 2 réponses, juste pour confirmer son calcul.
#22 - 21-01-2020 15:28:37
- CptFlaf
- Amateur de Prise2Tete
- Enigmes résolues : 0
- Messages : 3
naons et chapeaux
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.
#23 - 21-01-2020 18:01:10
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,969E+3
nains et chapeaix
Bonsoir, je pense que tu n'as pas saisi l'astuce de ce qu'est un modulo : Un exemple avec 6 nains et 6 couleurs, ils se sont mis d'accord pour attribuer une valeur de 0 à 5 à chaque couleur.
Le premier voit J+V+V+R+B = 2 + 3 + 3 + 0 + 4 = 12 soit 0 modulo 6. Le 0 correspondant au rouge, il dit "ROUGE" (Pas de bol, ce n'est pas sa couleur, mais il n'avait rien à perdre...) seulement, maintenant, les autres connaissent la somme de tous leurs chapeaux.
Le second voit V+V+R+B = 3 + 3 + 0 + 4 = 10 , et il sait donc que sont chapeau ne peut valoir que 2 soit "JAUNE"
Le troisième voit V+R+B = 3 + 0 + 4 , mais il n'oublie pas de rajouter le "JAUNE" entendu, ce qui donne 3 + 0 + 4 + 2 = 9 et il sait que son chapeau vaut 3. ...etc
Et le premier a bien juste dit une couleur et une seule.
#24 - 21-01-2020 22:26:33
Nians et chapeaux
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!
#25 - 23-01-2020 00:56:57
- godisdead
- Expert de Prise2Tete
- Enigmes résolues : 22
- Messages : 747
Nains et chpeaux
@mad : Si on prend le dessin de gwen. Le premier nain dit jaune (et meurt) Le deuxième dit vert (et meurt) Le troisième dit vert (et vit !!!!) Le quatrième qui rouge et meurt etc. Un survivant ... Bref, j'imagine que tu souhaitais dire que le dernier donne une info a celui qui est devant lui. Le suivant ne peut donner la couleur de son chapeau et donner une information au suivant ! Donc un sur 2 mort !
Mots clés des moteurs de recherche
|
|