Les nains et le bourreau

Olympiades mathématiques, énigmes et défis
Jacques Lavau
Membre Relatif
Messages: 118
Enregistré le: 19 Juin 2006, 02:19

C'est la roulette russe, à une chance sur 2, pour le premier

par Jacques Lavau » 03 Juil 2006, 23:16

Sdec25 a écrit:C'est pas de la roulette russe, le but est de sauver le plus de nains.

C'est la roulette russe, à une chance sur 2, pour le premier interrogé.
Après quoi le système est entièrement déterministe pour tous les suivants : chacun est exactement renseigné par le nain qui est derrière lui.
D'un seul mot ; je le précise pour ceux qui ont du mal à compter jusqu'à un sans s'embrouiller.



Sdec25
Membre Irrationnel
Messages: 1002
Enregistré le: 17 Juin 2006, 02:24

par Sdec25 » 03 Juil 2006, 23:30

Jacques Lavau a écrit:C'est la roulette russe, à une chance sur 2, pour le premier interrogé.
Après quoi le système est entièrement déterministe pour tous les suivants : chacun est exactement renseigné par le nain qui est derrière lui.
D'un seul mot ; je le précise pour ceux qui ont du mal à compter jusqu'à un sans s'embrouiller.


Oui ça l'est pour le premier.
Mais si j'ai bien compris, un nain se fait tuer si la couleur qu'il dit n'est pas celle de son chapeau.

En clair, chaque nain, qui n'a le droit de prononcer qu'un seul mot, doit prononcer la couleur de son chapeau.
S'il prononce la couleur du chapeau de celui qui le précède, il a une chance sur 2 de se faire tuer.
Dans le pire des cas, si la couleur change à chaque nain, seul le dernier survit.

J'ai beau relire l'énoncé de l'énigme et je ne comprend pas comment, en disant une seule couleur (celle de notre chapeau) on arrive aussi à renseigner le prochain nain sur la couleur du sien.

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 23 Aoû 2005, 01:53

par Patastronch » 03 Juil 2006, 23:37

je comprends pas ta solution jacques, le gars pour se libérer il doit dire la couleur de son chapeau pas dire la couleur du chapeau du mec en face. Par conséquent un gars soit il se libere soit il renseigne le suivant mais il peut pas faire les deux ou alors justement y a une feinte que j'ai pas capté.

[EDIT : grilled par Sdec25]

La solution de la parité fonctionne par contre sans aucun probleme, je suis tombé sur la meme solution en cherchant.

Sdec25
Membre Irrationnel
Messages: 1002
Enregistré le: 17 Juin 2006, 02:24

par Sdec25 » 03 Juil 2006, 23:48

En plus ça ne sert à rien de donner la couleur du chapeau du nain qui nous précède puisqu'il ne l'utilisera pas.

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 23 Aoû 2005, 01:53

par Patastronch » 03 Juil 2006, 23:50

Doit y avoir un truc qu'on a pas capté il a l'air sur de lui, mais ca serait bien qu'il nous explique.

Jacques Lavau
Membre Relatif
Messages: 118
Enregistré le: 19 Juin 2006, 02:19

Soit tu n'as pas lu l'énoncé

par Jacques Lavau » 03 Juil 2006, 23:52

Sdec25 a écrit:Oui ça l'est pour le premier.
Mais si j'ai bien compris, un nain se fait tuer si la couleur qu'il dit n'est pas celle de son chapeau.

En clair, chaque nain, qui n'a le droit de prononcer qu'un seul mot, doit prononcer la couleur de son chapeau.
S'il prononce la couleur du chapeau de celui qui le précède, il a une chance sur 2 de se faire tuer.
Dans le pire des cas, si la couleur change à chaque nain, seul le dernier survit.

J'ai beau relire l'énoncé de l'énigme et je ne comprend pas comment, en disant une seule couleur (celle de notre chapeau) on arrive aussi à renseigner le prochain nain sur la couleur du sien.

Soit tu n'as pas lu l'énoncé, soit tu l'as remplacé par un autre qui te convient mieux, pour lecteur entiché d'individualisme.
Rappel :
- Des nains sont disposés en file indienne, chacun regardant devant lui. Chaque nain a un chapeau blanc ou noir (chapeaux distribués aléatoirement).
Un bourreau arrive vers le dernier nain de la file (celui qui voit tt le monde) et lui demande la couleur de son chapeau : s'il a juste il vit, sinon il meurt. Puis il recommence avec l'avant dernier nain etc...(les nains ne peuvent repondre que "noir" ou "blanc" exclusivement)
- Les nains ont mis au point une stratégie pour qu'il y ait au pire 1 seul mort : laquelle ?

Si les nains ont mis au point une stratégie où au maximum un seul d'entre eux est perdu, ils ont raisonné en collectivité, et non en individualistes, où chacun ruse contre tous les autres.
C'est comme les suricates de Namibie. Pendant qu'ils s'ébattent et se ravitaillent, un guetteur veille sur un arbre. Il a deux cris d'alerte différents : un pour danger venant des airs, un pour danger au sol. Si c'est une attaque d'un aigle de Verreaux, la sentinelle est en grand danger d'être capturée, pendant que les autres se mettent à couvert. Les suricates ont une stratégie de collectivité.

Ici les nains sont perdus, en moyenne un sur deux, s'ils se comportent en individualistes, chacun pour son chapeau.
Alors qu'ils en perdent au maximum un seul, si chacun est la vigie du suivant dans la liste des interrogés. Chacun ne fait qu'une seule chose : renseigner le suivant, lui donner une information exacte.

BancH
Membre Irrationnel
Messages: 1317
Enregistré le: 17 Mar 2006, 23:50

par BancH » 03 Juil 2006, 23:54

Non y a rien, soit il s'est trompé soit il a mal compris.

Sdec25
Membre Irrationnel
Messages: 1002
Enregistré le: 17 Juin 2006, 02:24

par Sdec25 » 04 Juil 2006, 00:02

Jacques Lavau a écrit:Soit tu n'as pas lu l'énoncé, soit tu l'as remplacé par un autre qui te convient mieux, pour lecteur entiché d'individualisme.
Rappel :

Si les nains ont mis au point une stratégie où au maximum un seul d'entre eux est perdu, ils ont raisonné en collectivité, et non en individualistes, où chacun ruse contre tous les autres.
C'est comme les suricates de Namibie. Pendant qu'ils s'ébattent et se ravitaillent, un guetteur veille sur un arbre. Il a deux cris d'alerte différents : un pour danger venant des airs, un pour danger au sol. Si c'est une attaque d'un aigle de Verreaux, la sentinelle est en grand danger d'être capturée, pendant que les autres se mettent à couvert. Les suricates ont une stratégie de collectivité.

Ici les nains sont perdus, en moyenne un sur deux, s'ils se comportent en individualistes, chacun pour son chapeau.
Alors qu'ils en perdent au maximum un seul, si chacun est la vigie du suivant dans la liste des interrogés. Chacun ne fait qu'une seule chose : renseigner le suivant, lui donner une information exacte.


Chaque nain renseigne le suivant sur la liste, ça permet au suivant de savoir quelle est la couleur de son chapeau.
Seulement, le suivant n'utilise pas l'information donc il a aussi une chance sur 2 de se tromper.

BancH
Membre Irrationnel
Messages: 1317
Enregistré le: 17 Mar 2006, 23:50

par BancH » 04 Juil 2006, 00:04

C'est plutôt toi qui n'a pas bien lu l'énoncé.

S'il y a trois nains, et que les trois chapeaux du dernier au premier sont de couleurs : blanc, noir, blanc

D'après toi chaque nain dit la couleur du chapeau qu'il voit devant lui :

Le premier nain dit "noir" il crève.
Le second nain dit "blanc" il crève.
Le troisième nain est le seul à survivre.

Comprends-tu ?

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 23 Aoû 2005, 01:53

par Patastronch » 04 Juil 2006, 00:07

Sdec25 a écrit:Chaque nain renseigne le suivant sur la liste, ça permet au suivant de savoir quelle est la couleur de son chapeau.
Seulement, le suivant n'utilise pas l'information donc il a aussi une chance sur 2 de se tromper.


Ok donc la solution de Jacques est nulle on est d'acccord maintenant qu'on a bien compris ce qu'il a dit. Par contre la solution avec la parité permet d'en sauver 99 sur, et le premier a une chance sur deux ce qui est pas mal et qui correspond a l'énnoncé d'un sacrifié au max. On ne peux en sauver 100 de maniere sure car il faut une information de départ que le premier n'a pas en sa possession. Je doute qu'on puisse augmenter la survie du premier a plus d'une chance sur 2 pour la meme raison.

Sdec25
Membre Irrationnel
Messages: 1002
Enregistré le: 17 Juin 2006, 02:24

par Sdec25 » 04 Juil 2006, 00:13

On est d'accord. Et pour reprendre un exemple que j'ai déjà cité, si la couleur est alternée pour chaque nain, seul le dernier survit.

Je pense aussi que le premier a une chance sur 2, puisqu'au départ il ne dispose d'aucune information.

Jacques Lavau
Membre Relatif
Messages: 118
Enregistré le: 19 Juin 2006, 02:19

Il est donc sourd ?

par Jacques Lavau » 04 Juil 2006, 00:53

Sdec25 a écrit:Chaque nain renseigne le suivant sur la liste, ça permet au suivant de savoir quelle est la couleur de son chapeau.
Seulement, le suivant n'utilise pas l'information donc il a aussi une chance sur 2 de se tromper.

Il est donc sourd, selon toi ?
Il est vrai que l'info "sourd ou entendant" n'est pas explicite dans l'énoncé.
Mais la surdité de chacun à la parole du précédent rend inefficace toute stratégie de groupe.

De même que n'était pas explicite l'hypothèse pourtant indispensable, que les nains aient eu l'occasion de se concerter pour élaborer une stratégie de survie maximale, entre le moment où on leur annonce la règle du jeu, et le moment où on les aligne en file indienne, puis on les coiffe.
Il n'était pas non plus explicite qu'on les mette en file indienne après leur avoir appris la règle du jeu.
Mais là encore, sans cette hypothèse, pas de stratégie possible.

BancH
Membre Irrationnel
Messages: 1317
Enregistré le: 17 Mar 2006, 23:50

par BancH » 04 Juil 2006, 01:25

Jacques tu n'as rien compris, les nains ne peuvent dire qu'un seul mot, "noir" ou "blanc" et pas les deux, soit le nain dit la couleur de son chapeau soit la couleur du chapeau de celui devant lui, mais pas les deux.

Sdec25
Membre Irrationnel
Messages: 1002
Enregistré le: 17 Juin 2006, 02:24

par Sdec25 » 04 Juil 2006, 01:33

Jacques Lavau a écrit:Il est donc sourd, selon toi ?
Il est vrai que l'info "sourd ou entendant" n'est pas explicite dans l'énoncé.
Mais la surdité de chacun à la parole du précédent rend inefficace toute stratégie de groupe.

De même que n'était pas explicite l'hypothèse pourtant indispensable, que les nains aient eu l'occasion de se concerter pour élaborer une stratégie de survie maximale, entre le moment où on leur annonce la règle du jeu, et le moment où on les aligne en file indienne, puis on les coiffe.
Il n'était pas non plus explicite qu'on les mette en file indienne après leur avoir appris la règle du jeu.
Mais là encore, sans cette hypothèse, pas de stratégie possible.

Supposont que les nains ont une ouïe assez bonne pour entendre ce que leur dit le nain de derrière.

1 : Le nain entend la couleur de son chapeau
2 : Le nain est content puisqu'il connaît la couleur de son chapeau.
Mais le nain s'en fout, il dit la couleur de celui de devant.
3 : Pas de chance la couleur du nain de devant n'est pas la même que sa couleur donc le nain se fait tuer
Aïe.

EDIT : comme l'a dit Banch les nains ne peuvent dire qu'un seul mot. Mais ça Jacques le savait. Sinon le premier nain dirait toutes les couleurs des chapeaux.

Jacques Lavau
Membre Relatif
Messages: 118
Enregistré le: 19 Juin 2006, 02:19

OK j'ai faux.

par Jacques Lavau » 04 Juil 2006, 02:04

OK j'ai faux.
Ce qui était correct, c'est qu'il n'y a de stratégie conforme à l'énoncé que si passé le premier mot, toute la suite est déterministe.

La contradiction que je n'avais pas vue, est que dès le second nain doit parler, il doit transmettre deux infos en tout :
Une explicite au bourreau, où il énonce correctement la couleur de son chapeau à lui.
Une seconde, cachée au bourreau, mais destinée au condamné suivant, logiquement découplée de la première.
Mais sacrebleu ! C'est de l'oral ! Il reste donc toutes les ressources de la prosodie et de l'intonation. Les aphasiques du type Wernicke (ils n'ont plus la compréhension des mots, et ne peuvent plus en énoncer de sensés) s'en servent bien. Nos clébards, nos bébés et nos chevaux aussi, du reste.

Ils peuvent donc encoder l'info de plusieurs manières :
- Si ma voix est haut perchée, vous avez blanc.
- Si ma voix est haut perchée, vous avez la même couleur que celle que j'énonce pour moi.
- Si je bégaie en énonçant ma couleur, vous avez l'autre.
Etc.

Le tout est d'en choisir une, fiable, comprise et praticable par tous.

BancH
Membre Irrationnel
Messages: 1317
Enregistré le: 17 Mar 2006, 23:50

par BancH » 04 Juil 2006, 02:46

J'y avait pensé aussi, mais ça se voit que ce n'est pas la réponse attendue.

nox
Membre Complexe
Messages: 2157
Enregistré le: 14 Juin 2006, 11:32

par nox » 04 Juil 2006, 10:31

ba la réponse basée sur la parité ne vous satisfait pas?

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 23 Aoû 2005, 01:53

par Patastronch » 04 Juil 2006, 13:45

D'autant plus que l'intonation de la voix est un critere trop subjectif pour etre sur a 100% selon moi.

Jacques Lavau
Membre Relatif
Messages: 118
Enregistré le: 19 Juin 2006, 02:19

Autre solution : codage grammatical

par Jacques Lavau » 04 Juil 2006, 14:45

Patastronch a écrit:D'autant plus que l'intonation de la voix est un critere trop subjectif pour etre sur a 100% selon moi.

Autre solution : codage grammatical.
Si je dis "Blanche" et non "Blanc", ou "Noire" et non "Noir", c'est que tu as la couleur contraire à celle que j'énonce.

BancH
Membre Irrationnel
Messages: 1317
Enregistré le: 17 Mar 2006, 23:50

par BancH » 04 Juil 2006, 15:01

Ogre : De quelle couleur est ton chapeau sâle nain ?
Nain : Blanche
Ogre : ...

Vraiment discrette comme stratégie.

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 5 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite