[Jeu] Les énigmes dans le noir

De nombreux prisonniers sont invités à un jeu. Ils peuvent se rassembler et se mettre d'accord sur une stratégie, puis par la suite chacun sera enfermé dans une cellule individuelle de façon à ne plus pouvoir communiquer avec les autres. Régulièrement, un prisonnier est choisi au hasard et est conduit dans une salle ne comprenant qu'une lampe, qu'il peut choisir d'allumer ou d'éteindre. Seuls les prisonniers sont autorisés à y toucher, et au début du jeu elle commence éteinte. A tout moment un prisonnier peut affirmer que tous les prisonniers sont entrés au moins une fois dans la salle. S'il a raison ils sont libérés, sinon ils sont exécutés. Quelle stratégie permettrait au groupe d'être libéré ?

Les prisonnier peuvent être appelé plusieurs fois dans la salle ?

Oui. A chaque fois on tire au hasard parmi tous les prisonniers, qu'ils soient déjà venus ou non.

(Cela fait plus d'un mois que j'ai la solution, je ne l'avais pas écrite publiquement car je n'avais pas de bonne énigme a proposée ensuite)

Les prisonniers désignent un prisonnier unique, que j'appelle Treant (dans la grande tradition cryptographique).

Treant utilise l'algo suivant:
Il garde en mémoire un entier initialement a 0.
Si la lampe est allumée, alors il incrémente l'entier, il éteint la lampe puis si l'entier est égal au nombre de prisonniers moins 1, il demande la libération du groupe.

Chaque autre prisonnier utilise l'algo suivant:
Il garde en mémoire un booléen initialement a faux.
Si la lampe est éteinte et que le booléen en mémoire est a faux, alors il place le booléen a vrai et active la lampe. Sinon, il ne fait rien.

Bravo !

Bon, le premier qui a une énigme sympa en tête peut prendre la main.

Trois dieux A, B et C se nomment Vérité, Mensonge et Hasard (vous ne savez pas quel dieu est qui). Lorsqu'on leur pose une question, Vérité répond toujours la vérité, Mensonge répond toujours le contraire de la vérité, et Hasard répond toujours au hasard entre la vérité et son contraire. Votre tâche est de déterminer l'identité de ces trois dieux, à l'aide de trois questions fermées.
Les dieux comprennent parfaitement le français et la logique, mais ils ne répondront que dans leur propre langue qui ne possèdent que deux mots, « da » et « ja ». Ces mots signifient « oui » et « non », mais vous ne savez pas lequel se rapporte à quoi (!).

Indice ?

Vous vous êtes probablement déjà aperçu que cette énigme ressemblait à l'énigme plus simple suivante :

Il y a deux chemins et un garde devant chaque chemin. Un chemin conduit vers la liberté et l'autre vers une mort certaine. Un garde ment toujours, l'autre dit toujours la vérité. Contrairement à vous, eux savent où est le bon chemin et qui est qui. Quelle question fermée (dont la réponse est oui ou non) permettrait de trouver le bon chemin ?

D'habitude on essaie de faire intervenir dans la question les deux gardes pour qu'ils s'annulent (en un sens), mais il existe une solution ne faisant intervenir que le garde à qui on pose la question.

Indice : cette solution peut être transposée à l'énigme en cours pour simplifier sa résolution.

Vous voulez un indice de plus ?

J'ai une demi-réponse à la version simple de l'énigme !

« Est-ce que si l'autre garde me disait que ce chemin est le bon, ce serait un mensonge ? »
Si le garde plante et s'autodétruit, c'est qu'il disait la vérité et que c'était le bon chemin

(S'il répond non, on est devant le garde menteur du mauvais chemin. Et s'il répond oui, on n'a plus qu'à faire confiance à sa chance.)

(Bon, il est tard, j'avais l'intention de réfléchir à l'énigme, mais en fait je suis brainless. Peut-être une réponse un peu plus sérieuse un autre jour.)

Moi j'ai une question !!

Quand on pose une question, est-ce que les trois répondent ou est-ce que la question doit être ciblé ?

Ciblée.

Indice !

Dans l'énigme où il n'y que Vérité et Mensonge gardant un chemin bénéfique et un chemin néfaste, généralement on utilise la question suivante :

Si je demandais à ton collègue s'il garde le chemin bénéfique, que me répondrait-il ?

En effet si je suis face à Vérité il me dira ce que répondrait l'autre.
Mensonge me dirait oui s'il garde le chemin néfaste, et non s'il garde le chemin bénéfique.
Donc dans ce cas un oui signifie que le chemin face à moi est bénéfique, et un non qu'il est néfaste.
A l'inverse si je suis face à Mensonge il me répondrait le contraire de l'autre.
Vérité me dirait non s'il garde le chemin néfaste, et oui s'il garde le chemin bénéfique.
Donc dans ce cas aussi un oui signifie que le chemin face à moi est bénéfique, et un non qu'il est néfaste.
Dans tous les cas, un oui nous permet d'emprunter le chemin face à nous, et un non d'emprunter l'autre, sans risquer de se tromper.

Mais cette question fait appel aux deux gardes. Il existe aussi une possibilité en n'utilisant que le garde en face de soi :

Si je te demandais si tu gardes le chemin bénéfique, que me répondrais-tu ?

Si je demandais à Vérité s'il garde le chemin bénéfique, il me dirait oui s'il garde le chemin bénéfique et non s'il garde le chemin néfaste. Donc si je lui demande ce qu'il me dirait si je lui posais la question, il me répondra oui s'il garde le chemin bénéfique et non s'il garde le chemin néfaste.
Si je demandais à Mensonge s'il garde le chemin bénéfique, il me dirait non s'il garde le chemin bénéfique et oui s'il garde le chemin néfaste. Donc si je lui demande ce qu'il me dirait si je lui posais la question, il me répondra oui s'il garde le chemin bénéfique et non s'il garde le chemin néfaste.
Dans tous les cas, le oui correspond au chemin bénéfique et le nom au chemin néfaste.

Cette solution est plus simple car elle ne fait pas appel aux autres gardes, ce qui facilite la résolution de l'énigme avec trois gardes.

Peut-être serait-il plus clair d'expliciter le comportement de Hasard ?

Quand on lui pose une question il lance pour lui seul une pièce : si le résultat est pile alors il répondra à la question en temps que Vérité, et si la pièce est face alors il répondra à la question en temps que Mensonge.

J'espère que cela va vous donner des idées... car si personne ne trouve la réponse d'ici un mois jour pour jour je me couronnerai Prince des Énigmes, puis je donnerai un paradoxe avant de passer la main.

Il est enfin temps de donner la solution !
Vous qui n'avez pas trouvé, consolez-vous en apprenant que cette énigme est généralement appelée « L'Énigme la plus difficile du monde ». Maintenant que vos égos meurtris sont pansés, passons au détail de la solution...

J'ai donné comme indice d'utiliser une question de la forme "Si je te demandais si tu gardes le chemin bénéfique, que me répondrais-tu ?" dans l'énigme des deux gardiens au lieu de la solution habituelle "Si je demandais à ton collègue s'il garde le chemin bénéfique, que me répondrait-il ?". L'intérêt est d'utiliser une telle question sur un seul garde, indépendamment du fait qu'il y ait un ou plusieurs autres gardes. Cela fonctionne si nous tombons sur Vérité ou Mensonge. Mais qu'en est-il de Hasard ?
J'ai pris la peine d'expliciter le comportement de Hasard, à savoir qu'il tire au sort avant que je pose la question s'il répondra comme Vérité ou Mensonge, et ensuite répondra en accord avec son état mental. Si je lui pose une autre question il pourra changer de rôle, mais ce qui importe est qu'il agisse comme l'un ou l'autre. Ainsi, comme une question de la forme "Si je te demandais si tu gardes le chemin bénéfique, que me répondrais-tu ?" fonctionne pour les deux rôles, elle fonctionnera également pour Hasard.
Mais ici nous ne nous intéressons pas à des portes mais aux identités de chacun. Il faudrait donc une question de la forme "Si je te demandais "Es-tu Hasard ?", que me répondrais-tu ?". Le problème est que les dieux ne répondent pas par oui ou non, mais par ja ou da, sans que nous sachions lequel signifie oui et lequel signifie non. Donc en fait il faudrait plutôt une question de la forme "Si je te demandais "Es-tu Hasard ?", répondrais-tu ja ?".

Là il faut prendre des pincettes pour comprendre la réponse qu'un dieu ferait à une telle question.
Je ne vais pas vous faire toute la table de vérité, que vous trouverez dans l'article en anglais, mais l'idée est que la réponse à la question "Si je te demandais Q, répondrais-tu ja ?" (où Q est une question) va dépendre :
- de la réponse véritable à Q
- du rôle du dieu en face
- de la signification de ja et da
Il se trouve qu'en évaluant les huit cas possibles, on s'aperçoit que la réponse à "Si je te demandais Q, répondrais-tu ja ?" est ja si et seulement si la réponse véritable à Q est oui, et ce indépendamment du rôle du dieu ou de la signification de ja.
Ainsi, si nous posons la question "Si je te demandais "Es-tu Hasard ?", répondrais-tu ja ?" à A, deux cas sont possibles :
1) A répond ja et alors nous savons que la réponse à la question "Es-tu Hasard ?" est oui. Comme A est Hasard, demandons à présent à B "Si je te demandais "Es-tu Vérité ?", répondrais-tu ja ?". S'il répond ja alors B est Vérité donc C est Mensonge, et s'il répond da alors B est Mensonge et C est Vérité.
2) A répond da et alors nous savons que la réponse à la question "Es-tu Hasard ?" est non. Il faut alors demander à A "Si je te demandais "Es-tu Vérité ?", répondrais-tu ja ?", s'il répond ja alors il est Vérité et sinon il est Mensonge. Ensuite il suffit de demander à B s'il est Hasard pour déduire le rôle des deux autres.

Il est notable que dans le premier cas seules deux questions sont utilisées sur les trois. Si on change le comportement de Hasard de façon à ce que c'est la réponse elle-même qui est tirée au sort et non le rôle, il faut alors utiliser trois questions dans tous les cas. Si jamais il est supposé que la tête d'un dieu explose si on lui pose un paradoxe, alors de façon assez compliquée il est prouvable que seules deux questions sont nécessaires. Les détails sont dans l'article en anglais si jamais vous êtes curieux.

Il me semble donc que mon règne de Prince des Énigmes peut enfin commencer !
Voici pour la route une petit vidéo contenant des paradoxes, et je laisse la main à qui veut la prendre...

L'énigme qui m'a accordé mon titre a été esquissée dans ce taupe 10 avec d'autres énigmes intéressantes (je ne les connaissais même pas toutes ^^).