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 hcapeaux

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

nains et xhapeaux

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

Nains et capeaux

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 chappeaux

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

nains rt 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 : 3823
Lieu: hébesphénorotonde triangulaire

Nains et chapeux

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

Nains et chapaux

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

Nains et chapeuax

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

Nains et chapeaaux

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

naons et 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

bains et 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 et chapeaxu

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

Nains e 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 : 439

Nains et chapeauxx

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

nains et chapraux

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

Nains et chapeauxx

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

NNains 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 : 439

nains et cgapeaux

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

Nains et chhapeaux

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 et chapeaaux

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

Nains e tchapeaux

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 (numériquement) à la petite énigme suivante : 

Dans une course, vous doublez le 31ème, en quelle position êtes-vous ?

Sujets similaires

Sujet Date Forum
P2T
Encore des chapeaux! par PRINCELEROI
22-10-2013 Enigmes Logiques
P2T
Les chapeaux par jeansayrien
13-02-2009 Enigmes Logiques
P2T
16-01-2008 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
Escalier et chapeaux par McFlambi
21-06-2010 Enigmes Logiques
P2T
Mat en 3 coups (2) par L00ping007
25-03-2011 Enigmes Logiques
26-09-2010 Enigmes Logiques

Mots clés des moteurs de recherche

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