Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #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?

  • |
  • Répondre

#0 Pub

 #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...
smile 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 ? big_smile


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 lol


"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? lol

 #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 ?
mad


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 roll


"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 ! wink


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. smile


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 big_smile
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 ! smile


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

Ca finit par devenir prenant ce truc smile

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 big_smile pour qu'on se vrille totalement lol

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. smile

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 big_smile


"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.

http://www.prise2tete.fr/upload/gwen27-chpnainsPNG.png

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

Mad217
Visiteur

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 ... smile
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 !

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Si il y a 78 pommes et que vous en prenez 43, combien en avez-vous ?

Sujets similaires

Sujet Date Forum
P2T
Encore des chapeaux! par PRINCELEROI
22-10-2013 Enigmes Logiques
P2T
16-01-2008 Enigmes Logiques
06-06-2008 Enigmes Logiques
P2T
Les chapeaux par jeansayrien
13-02-2009 Enigmes Logiques
P2T
Les 6 chapeaux ! par Azdod
06-11-2012 Enigmes Logiques
P2T
Escalier et chapeaux par McFlambi
21-06-2010 Enigmes Logiques
P2T
Les 3 chapeaux par EfCeBa
22-02-2008 Enigmes Logiques
12-11-2008 Enigmes Logiques
P2T
25-08-2012 Enigmes Logiques

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete