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 rt chapeaux

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?



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 27-05-2016 20:09:31

Klimrod
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 3758
Lieu: hébesphénorotonde triangulaire

Nains te chapeaux

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 : 1740

Nains et chapeax

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 : 2124

nains et cgapeaux

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 : 1203

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 : 3758
Lieu: hébesphénorotonde triangulaire

nains et cgapeaux

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 : 3311

Nains et chapeax

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 : 3758
Lieu: hébesphénorotonde triangulaire

Nains et chapeauxx

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 : 1064

Naisn 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 : 3758
Lieu: hébesphénorotonde triangulaire

nains er 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 : 2989
Lieu: Fanning Island-?-Lac Tele,Mali

nains et chaoeaux

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 : 2124

Nains eet 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 : 3758
Lieu: hébesphénorotonde triangulaire

naibs et chapeaux

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
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 400

nains et chapzaux

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 : 3758
Lieu: hébesphénorotonde triangulaire

nains et chapeauw

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,464E+3

Nains et hapeaux

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 : 3758
Lieu: hébesphénorotonde triangulaire

Nainns 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
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 400

Nains et cchapeaux

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,464E+3

nains et chapezux

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 : 2124

Nain et 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,464E+3

Nais et chapeaux

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.

 

Réponse rapide

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

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pif, Paf et ?

Sujets similaires

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

Mots clés des moteurs de recherche

Mot clé (occurences)

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