Je me suis attaqué à l’énigme la plus difficile du monde.
Ce célèbre problème publié dans un article par George Boolos en 1996 a même une page Wikipedia traduite en 16 langues.
Énoncé
Derrière trois personnages A, B et C se cachent les dieux Vrai, Faux et Aléatoire.
Vrai répond toujours la vérité, Faux répond toujours le contraire de la vérité, et Aléatoire choisit ses réponses au hasard.
Votre tâche est de dévoiler les identités de A, B et C en posant uniquement trois questions dont la réponse est vrai ou faux.
Les dieux comprennent le français mais ils répondront à vos questions dans leur propre langue, c'est-à-dire par da et ja.
Vous ne savez pas à quoi ces réponses correspondent.
Boolos ajoute les clarifications suivantes :
Vous pouvez interroger un dieu plusieurs fois (et alors un dieu ne sera pas du tout questionné).
La deuxième question et à qui s'adresse celle-ci peut dépendre de la réponse à la première question. De même pour le choix de la troisième.
Aléatoire peut être considéré comme décidant ses réponses à toute question vrai-faux par un jet à pile ou face : si la pièce tombe sur face, il dira da ; si elle tombe sur pile, ja.
Voilà comment je m’en suis sorti :
Comment résoudre l’énigme la plus difficile du monde ?
Notation : Pour ce qui va suivre, je vais noter les dieux avec des majuscules : Vrai, Faux et Aléatoire, et les réponses vrai et faux correspondants à da et ja en italique.
Accrochez-vous.
Les étapes
Nous avons le doit à trois questions.
Pour chaque question, nous allons procéder par étapes :
- Comprendre l’objectif de la question.
- Déterminer le pattern recherché.
- Trouver la question qui répond à ce pattern.
Pour mettre le doigt sur les bons objectifs, il nous faut déjà comprendre comment les dieux vont se comporter en testant des questions.
Simplifions l’énigme en enlevant Aléatoire.
Il se trouve que ce problème se résout en une seule question.
- L’objectif de la question est de déterminer qui est Vrai, et qui est Faux.
- On cherche donc un schéma où Vrai répondra toujours de la même manière, et Faux toujours de l’autre. Par exemple :
- La question : “Est-ce que da veut dire vrai” engendre ce pattern et permet par la même occasion de nous affranchir de la signification de da et ja.
Vérification
Cas 1 : da veut bel et bien dire vrai (et ja = faux)
Si je pose la question à Vrai, il dira la vérité, à savoir vrai, donc da.
Si je pose la question à Faux, il va mentir, à savoir faux, et répondra ja.
Cas 2 : da veut dire faux (et ja = vrai)
Si je pose la question à Vrai, il dira la vérité, à savoir faux, donc da.
Si je pose la question à Faux, il va mentir, à savoir vrai, et répondra ja.
En posant la question “Est-ce que da veut dire vrai” à l’un des deux, on peut donc conclure qui il est, à savoir Vrai s’il répond da, et Faux s’il répond ja. Puis, il suffit de déduire l’identité du second dieu.
Raisonnement
Aléatoire est le relou de l’énigme. Il complique tout. Il est impossible de tirer des conclusions lorsqu’il est dans les parages. La solution est radicale : l’écarter.
Voilà le raisonnement permettant de résoudre l’énigme :
- Déterminer un dieu qui n'est pas Aléatoire.
- Identifier ce dieu (Vrai ou Faux).
- Lui demander d'identifier l’un des deux restants.
- Déduire le troisième dieu.
La bonne nouvelle, c'est que nous avons déjà trouvé la question permettant de trancher entre Vrai et Faux : “Est-ce que da veut dire vrai ?”.
L’étape 2 revient au problème simplifié, sans Aléatoire.
Il nous reste donc les questions des étapes 1 & 3.
Commençons par l’étape 3. Faites-moi confiance, c’est plus simple ainsi.
Trouver Aléatoire
Imaginons que nous ayons réussi à identifier soit Vrai, soit Faux, et qu’il ne nous reste qu’une question. Alors, je peux pointer quelqu’un et lui demander si cette personne est Aléatoire.
Le pattern que l’on recherche est le suivant :
Si j’ai bien pointé Aléatoire, il faudrait que Vrai et Faux répondent la même chose, par exemple da.
Si je me suis trompé, il faudrait encore que Vrai et Faux répondent la même chose, mais cette fois ja.
Nous allons rentrer dans le domaine de la logique biconditionnelle.
On recherche une table de vérité de ce type :
Remplaçons V par da, et F par ja.
da par da = da
da par ja = ja
ja par da = ja
ja par ja = da
Nous allons nous en servir en posant une question dans la question.
Si c’est flou, la suite devrait vous éclairer.
Prenons une vérité admise pour comprendre le comportement de Vrai et Faux.
Considérons la question suivante : “Si je te demandais si 1+1=2, est-ce que tu répondrais da ?
Vrai va dire deux fois la vérité, et Faux mentir deux fois.
Remplacez 1+1=2 par n’importe quelle affirmation vraie
→ Vrai ET Faux répondront da.
Remplacez 1+1=2 par n’importe quelle affirmation fausse
→ Vrai ET Faux répondront ja.
Nous allons donc pointer l’un des dieux non identifiés, en demandant au que l’on connaît : “Si je te demandais si ce dieu est Aléatoire, est-ce que tu répondrais da ?”
Si la réponse est da, alors nous sommes dans le cas d’une affirmation vraie. Le dieu pointé est bien Aléatoire.
Si la réponse est ja, alors nous sommes dans le cas d’une affirmation fausse. Le dieu pointé n’est pas Aléatoire.
À ce stade, deux dieux sont alors identifiés et le le dernier se trouve par déduction sans avoir à poser de question (étape 4).
La première question
J’ai gardé cette étape pour la fin car c’est peut-être la plus difficile à comprendre.
L’enjeu est le suivant :
Comment identifier, en une question, et à coup sûr, un dieu qui n’est PAS Aléatoire ?
Pour reprendre le raisonnement, si l’on y parvient, on pourra ensuite l’identifier (étape 2) puis, lui demander de nous indiquer qui est Aléatoire (étape 3), avant de déduire le dernier dieu (étape 4).
Nous allons de nouveau utiliser la logique biconditionnelle, en la couplant avec une dimension spatiale.
Imaginez que trois personnages A, B et C (les 3 dieux) se dressent face à vous.
Voilà toutes les configurations possibles :
Nous allons poser notre première question à B.
On cherche un pattern permettant d’isoler une colonne où Aléatoire n’est pas présent en fonction de la réponse.
La bonne question à poser à B est : “Si je te demandais si Aléatoire est à ta droite, est-ce que tu répondrais da ?”
Voyons les cas :
Isolons tous les cas où B répond ja :
Puis tous les cas où B répond da :
Si B répond ja, alors je pourrai poser la seconde question à C. Je serai alors certain qu’il ne s’agit pas d’Aléatoire.
Si B répond da, alors je pourrai poser la seconde question à A. Je serai alors certain qu’il ne s’agit pas d’Aléatoire.
La solution
Question n°1, à B : “Si je te demandais si Aléatoire est à ta droite, est-ce que tu répondrais da ?”
→ Si la réponse est da, A n’est pas Aléatoire.
→ Si la réponse et ja, C n’est pas Aléatoire.
Question n°2, pour identifier ce dieu (A ou C) : “Est-ce que da veut dire vrai ?”
→ Si la réponse est da, il s’agit de Vrai.
→ Si la réponse est ja, il s’agit de Faux.
Question n°3, pour lui demander d’identifier B : “Si je te demandais si B est Aléatoire, est-ce que tu répondrais da ?”
→ Si la réponse est da, B est Aléatoire.
→ Si la réponse et ja, B n’est pas Aléatoire. Il s’agit de Vrai si l’on pose la question à Faux, et inversement.
Une fois que l’on connaît l’identité de deux dieux, on peut déduire le troisième par élimination.
Et voilà comment on résoud l’énigme la plus difficile du monde.
