Le casse-tête de logique le plus dur jamais conçu

[switch]

La logique de certains m'est récemment apparue comme particulièrement incompréhensible. Voici de quoi travailler un peu le sujet (je n'ai aucun mérite, je l'ai trouvé sur le net) :

A, B et C représentent trois Dieux appelés, dans un certain ordre, Vrai, Faux et Aléatoire. Vrai dit toujours la vérité, Faux ment continuellement et Aléatoire n’en fait qu’à sa tête.

Votre tâche est de déterminer l’identité de A, B et C en posant trois questions de type oui-non. Chaque question doit être posée à un seul dieu. Ils comprennent le français, mais répondront à toutes les questions dans leur propre langue dans laquelle les mots pour «oui» et «non» sont «da» et «ja». Vous ne savez pas quel mot signifie quoi.’

[Etienne Beauman]

De prime abord je dirais qu'il est impossible d'être sûr d'identifier l’aléatoire avec seulement trois questions, il est probable que ses réponses soient identiques à un des deux autres.
Pour distinguer le groupe menteur/ aléatoire du groupe vérité/aléatoire je n'ai besoin que de deux questions.

[spin-up]

Horrible, l'aléatoire fout un bordel monstre.

Pour distinguer le groupe menteur/ aléatoire du groupe vérité/aléatoire

Qu'est ce que tu veux dire par là exactement? Que tu peux ientifier un groupe de 2 contenant Aleatoire et soit Vrai, soit Faux?

[spin-up]

Il manque quelque chose d'essentiel dans l'énoncé:

Aléatoire racontant ou pas la vérité peut être considéré comme un choix décidé par un jet à pile ou face : si la pièce tombe sur face, il ne dira que la vérité ; si elle tombe sur pile, il ne dira que des mensonges.

Ca veut dire qu'Aleatoire va avoir le même comportement (menteur ou honnete) si on lui pose plusieurs questions. En fait sans ca, je crois que ce serait completement impossible.

Du coup, je pense que je me rapproche de la solution.

[Eve_en_Gilles]

Je sais comment déterminer quel mot correspond à "oui" et quel mot correspond à "non" en une seule question.
Mais ca ne laisse plus que deux questions pour départager les 3 Dieux. Je sais le faire en 1 question avec juste Vrai et Faux, mais Aléatoire me bloque pour le moment.

[Etienne Beauman]

Que tu peux identifier un groupe de 2 contenant Aleatoire et soit Vrai, soit Faux?

C'est ça.

Il manque quelque chose d'essentiel dans l'énoncé:

Ok ça a plus de sens comme ça.
J'ai les 3 en trois questions.

[embtw]

Je connaissais déjà, pas sous cette forme-là, mais c'est généralement un des jeux de logique qu'on trouve dans les pages jeux d'été des magazines scientifiques vulgarisants chers à Gatti comme Science&Vie, Sciences&Avenir ou encore ça m'intéresse.

[Raphaël]

Scénario #1

On pose la question à A: Est-ce que la Lune est en fromage ?
S'il répond OUI c'est donc que A est Faux ou Aléatoire.

On pose la question à B: Est-ce que la Lune est en fromage ?
S'il répond OUI c'est donc que B est Faux ou Aléatoire.

C'est donc C qui est Vrai.

On pose la question à C: Est-ce A est Faux ?
et l'énigme est résolue.

* * *
Scénario #2

On pose la question à A: Est-ce que la Lune est en fromage ?
S'il répond NON c'est donc que A est Vrai ou Aléatoire.

On pose la question à B: Est-ce que la Lune est en fromage ?
S'il répond NON c'est donc que B est Vrai ou Aléatoire.

C'est donc C qui est Faux.

On pose la question à C: Est-ce A est Vrai ?
On prend le contraire de sa réponse et l'énigme est résolue.


* * *
Scénario #3

On pose la question à A: Est-ce que la Lune est en fromage ?
S'il répond OUI c'est donc que A est Faux ou Aléatoire.

On pose la question à B: Est-ce que la Lune est en fromage ?
S'il répond NON c'est donc que B est Vrai ou Aléatoire.

Je cherche encore la 3e question à poser...

[embtw]

[...]
Est-ce que la Lune est en fromage ?
[...]
Est-ce que la Lune est en fromage ?
[...]
Est-ce que la Lune est en fromage ?
[...]

Denis, sors de ce corps !

[Etienne Beauman]

S'il répond OUI

Il te répondra pas oui mais da ou ja.

[Raphaël]

S'il répond OUI

Il te répondra pas oui mais da ou ja.

Je le sais mais j'ai traduis les réponses.

[Etienne Beauman]

Chaque question doit être posée à un seul dieu.

Houla j'ai zappé ce point.
Ok j'ai rien pour l'instant

[lau'jik]

A, B et C représentent trois Dieux appelés, dans un certain ordre, Vrai, Faux et Aléatoire. Vrai dit toujours la vérité, Faux ment continuellement et Aléatoire n’en fait qu’à sa tête.

Votre tâche est de déterminer l’identité de A, B et C en posant trois questions de type oui-non. Chaque question doit être posée à un seul dieu. Ils comprennent le français, mais répondront à toutes les questions dans leur propre langue dans laquelle les mots pour «oui» et «non» sont «da» et «ja». Vous ne savez pas quel mot signifie quoi.’

En commençant à noircir mes p'tits bouts de papier j'ai eu un doute : cette phrase (en gras) signifie qu'on pose trois questions à chaque dieu ou une seule (on est bien d'accord il s'agit de questions différentes hein ?) à chaque dieu ?

Ah OK, la réponse est tombée pendant que j'écrivais.

[Etienne Beauman]

Ok !
Je crois que j'ai les trois avec une question à chacun.
édit
Non ça marche pas!
Je peux savoir c'est quoi oui c'est quoi non, si le second dis la vérité ou pas, si le troisième est ou pas l’aléatoire, s'il l'est je retrouve les deux autres mais s'il l'est pas je suis bloqué...

re-édit
Cette fois je le tiens j'ai affiné ma seconde question et tout semble correcte.

[lau'jik]

Je crois que je l'ai !


Ah ben non, j'ai été trop vite en besogne...

[syntaxerror]

" mais répondront à toutes les questions dans leur propre langue dans laquelle les mots pour «oui» et «non» sont «da» et «ja». Vous ne savez pas quel mot signifie quoi.’"

On comprend pas les mots qu'ils utilisent donc on ne sait pas si leur réponse et oui ou non?

[yquemener]

Il doit y avoir une astuce que je n'ai pas. Quelque soit la méthode utilisée, on ne peut être sur de ne pas s’adresser au dieu aléatoire. On est obligé de poser une question à chacun des dieux en sachant que l'aléatoire est parmi eux. On aura donc une réponse aléatoire, inutilisable, à jeter. Même en supposant qu'on puisse l'identifier, il ne nous reste que 2 bits d'informations, capables de discriminer entre 2^2 = 4 permutations. Or il y a 6 permutations possible des rôles.

A moins d'utiliser une astuce qui vrille les règles, ou qu'on me donne un moyen qui m'échappe pour utiliser une réponse directe du dieu aléatoire, je pense que ce n'est pas possible.

[Etienne Beauman]

Il doit y avoir une astuce que je n'ai pas. Quelque soit la méthode utilisée, on ne peut être sur de ne pas s’adresser au dieu aléatoire. On est obligé de poser une question à chacun des dieux en sachant que l'aléatoire est parmi eux. On aura donc une réponse aléatoire, inutilisable, à jeter. Même en supposant qu'on puisse l'identifier, il ne nous reste que 2 bits d'informations, capables de discriminer entre 2^2 = 4 permutations. Or il y a 6 permutations possible des rôles.

A moins d'utiliser une astuce qui vrille les règles, ou qu'on me donne un moyen qui m'échappe pour utiliser une réponse directe du dieu aléatoire, je pense que ce n'est pas possible.

As tu pris en compte ce que disait Spin-up ?

[yquemener]

J'ai vu ce que disait spinup, et je n'ai pas vu switch confirmer, c'est même en contradiction avec l'énoncé initial.

Dans ce cas là, ça devient possible selon le pur critère de l'information, mais à la condition de ne pas chercher à comprendre la signification de ja/da et de ne pas chercher à savoir si l'aléatoire ment ou dit vrai. Ça me parait dur mais je ne suis pas sur de pouvoir en prouver l'impossibilité du coup.

Est ce qu'il ne manquerait pas encore un truc dans l'énoncé ?

[Etienne Beauman]

J'ai vu ce que disait spinup, et je n'ai pas vu switch confirmer, c'est même en contradiction avec l'énoncé initial.

Dans ce cas là, ça devient possible selon le pur critère de l'information, mais à la condition de ne pas chercher à comprendre la signification de ja/da et de ne pas chercher à savoir si l'aléatoire ment ou dit vrai. Ça me parait dur mais je ne suis pas sur de pouvoir en prouver l'impossibilité du coup.

Est ce qu'il ne manquerait pas encore un truc dans l'énoncé ?

Nope.
En trois questions, on peut savoir ce que veut dire da et ja, et qui est qui, l'astuce est dans la formulation des questions c'est un peu la même chose que pour ce problème :
Sur le sentier de ta vie tu arrives à une fourche une des routes t’emmène là où tu désires aller l'autre te conduit à une mort certaine. Il y a deux diablotins aux environs, l'un dit toujours la vérité l'autre ment systématiquement mais tu ne sais pas qui est qui, t'as le droit de ne poser qu'une unique question à l'un d'entre eux pour trouver ta route.

edit :
Mais t'as raison je ne sais pas si l'aléatoire dit ou pas la vérité, mais on ne nous le demande pas.

[Eve_en_Gilles]

Nope.
En trois questions, on peut savoir ce que veut dire da et ja, et qui est qui, l'astuce est dans la formulation des questions c'est un peu la même chose que pour ce problème :
Sur le sentier de ta vie tu arrives à une fourche une des routes t’emmène là où tu désires aller l'autre te conduit à une mort certaine. Il y a deux diablotins aux environs, l'un dit toujours la vérité l'autre ment systématiquement mais tu ne sais pas qui est qui, t'as le droit de ne poser qu'une unique question à l'un d'entre eux pour trouver ta route.

Celle là je la maîtrise, mais j'arrive pas (encore) à correctement formuler les questions pour prendre en compte l'Aléatoire.

[Etienne Beauman]

Celle là je la maîtrise, mais j'arrive pas (encore) à correctement formuler les questions pour prendre en compte l'Aléatoire.

Bah je veux pas trop en dire pour pas gâcher le plaisir de chercher

[yquemener]

@Etienne : Justement, dans le problème que tu donnes, tu cherches une information codable sur un bit (le chemin à prendre) et tu as le droit de recueillir un seul bit en réponse, donc ça tient. L'astuce consiste à ne pas chercher quel diablotin est le menteur, car tu aurais alors besoin de deux bits d'info.

Là on nous demande de déterminer l'identité des 3 dieux, ce qui demande entre 2 et 3 bits, et on nous autorise 3 bits en réponse. En théorie, "ça tient", mais la réponse du dieu aléatoire, si elle était réellement aléatoire, est inutilisable, donc on se retrouve avec deux bits, c'est insuffisant.

C'est assez contre-intuitif, mais il semble clair que savoir ce que ja et da signifient rend impossible d'avoir toute l'info sur l'identité des dieux : c'est une info indépendante de leur identité, et elle prend 1 bit. S'il y a une solution, comme dans ton énigme des deux chemins qui passe par le fait que tu te moques de l'identité des diablotins, tu dois formuler tes questions pour que l'info soit codée dans les différences de réponse entre les questions, et donc ne pas savoir ce que ja et da singifient à la fin.

Si quelqu'un a la réponse, ça m'intrigue, dans les deux cas. L'énoncé original me semble impossible, et pour le deuxième, ça m'étonne que ce soit possible, mais j'aime être étonné

[Etienne Beauman]

L'énoncé original me semble impossible

A moi aussi.
Si tu veux mes réponses, euh mes questions, à l'énoncé rectifié par Spin-up, je te les envoye en mp sans explications dans un premier temps.

[lau'jik]

Bon ben moi je viens de trouver qui a posé (et résolu) cette énigme et ça en impose, je vais y aller mollo avec mon petit cerveau, s'agit pas qu'il grille !
Il me manque la clé du oui/non, pour le reste je m'en sort. Mais je me dis que j'ai trouvé le plus facile