L'énigme la plus difficile de TOUS LES TEMPS !!!!
On connaît tous l'énigme des deux portes :
Dans un labyrinthe, deux gardes protègent deux portes. L'une des deux portes mène à la liberté, l'autre à une mort certaine. L'un des deux gardes ment systématiquement, tandis que l'autre dit toujours la vérité, mais vous ne savez pas qui est qui. Pour déterminer le chemin de la liberté, vous n'avez le droit qu'à une seule question à l'un des deux gardes. Quelle question poser ?
Cette énigme, sous sa forme actuelle, a été popularisée par le film Labyrinthe (1986) de Jim Henson, avec David Bowie. Mais les problèmes de logique du style "l'un ment, l'autre dit la vérité" viennent essentiellement de l'esprit tordu du génial Raymond Smullyan, où il pose les bases en 1978 dans son livre "Quel est le titre de ce livre ?" (à feuilleter absolument !).
Pour déterminer le chemin vers la liberté, il suffit de poser à l'un des deux gardes la question :
Q : Si je demande à l'autre garde le chemin de la liberté, quelle porte m'indiquera-t-il ?
Puisque les deux gardes sont impliqués dans cette question, la réponse sera forcément un mensonge. Il suffit donc de choisir la porte qui n'a pas été indiquée par le garde pour garantir son accès à la liberté. Des questions alternatives sont possibles, notamment la suivante, qui a le mérite de ne pas faire intervenir les deux gardes dans l'histoire :
Q' : Si je vous demandais quel est le chemin de la liberté, quelle porte m'indiqueriez-vous ?
Si on pose la question "quel est le chemin de la liberté ?" au garde menteur, il indiquerait la porte de la mort. Sachant cela, il répondra donc à Q' le contraire, à savoir, la porte de la liberté. Quel que soit le garde à qui cette question est posée, la réponse que l'on obtiendra indiquera donc forcément le bon chemin (il faut admettre que les gardes raisonnent en parfaits logiciens, ce qu'il est préférable de vérifier avant de risquer sa vie en posant des questions tordues).
Ca, c'est l'énigme classique. Mais je suis tombé cette semaine sur une version alternative de l'énigme, sobrement intitulée :
L'énigme de logique la plus difficile de tous les temps
Cette énigme, attribuée à Raymond Smullyan a particulièrement été étudiée par le philosophe et logicien George Boolos. C'est dans un article du Harvard Review of Philosophy qu'il publie en 1996 l'énigme :
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 (!).
Quelques remarques tout de même : on peut poser plusieurs questions à un même dieu (mais pas plus de 3 en tout) ; la deuxième question que l'on posera peut dépendre de la réponse « da » / « ja » obtenue à la première réponse (idem pour la troisième) ; quand on pose une question à Hasard, il jette une pièce dans sa tête, et répondra la vérité s'il obtient pile, et le contraire de la vérité sinon.
Oui, cette énigme est particulièrement horrible. Si vous ne voulez pas vous faire spoiler la solution, arrêter tout de suite la lecture de cet article, et revenez dans quelques jours. Pour les autres, voici les questions à poser, selon l'article de Boolos :
Q1, à poser à A :
Est-ce que (« da » signifie « oui » si et seulement si vous êtes Vérité) si et seulement si B est Hasard ?
Q2 à poser à B si la réponse était « ja » ou à C si la réponse était « da » :
Est-ce que « da » signifie « oui » si et seulement si Rome est en Italie ?
Q3, à poser au même dieu que lors de question 2 :
Est-ce que « da » signifie « oui » si et seulement si A est Hasard ?
Si la réponse à Q2 est « da », le dieu ayant répondu à cette question est Vérité, sinon, c'est Mensonge.
Si Vérité a répondu à Q3, la réponse « da » signifie que A est Hasard, et la réponse « ja » signifie que A est Mensonge ;
Si Mensonge a répondu à Q3, la réponse « da » signifie que A est Vérité, et la réponse « ja » signifie que A est Hasard.
On connaît maintenant l'identité des trois dieux !
Oui, mais... pourquoi ?!
Rappelons que, en logique, le "si et seulement si" (ssi) désigne l'équivalence logique : l'expression "P ssi Q" est vraie lorsque les expressions P et Q sont soit toutes les deux vraies, soit toutes les deux fausses. Ainsi, l'expression "(P ssi Q) ssi R" sera vraie dans deux cas : lorsque P, Q et R sont toutes les trois vraies, ou lorsque exactement une seule des trois propositions est vraie.
On peut donc reformuler plus clairement Q1 par :
Est-ce qu'un nombre impair des affirmations suivantes sont vraies : « da » signifie « oui », vous êtes Vérité, B est Hasard ?
Cette question n'a que un seul but : déterminer un des deux dieux qui n'est pas Hasard, afin d'être certain de ne pas s'adresser à lui lors des questions Q2 et Q3.
Si A est Hasard, alors quelle que soit sa réponse, on sera amené à parler à B ou C lors des questions suivantes.
Dans le cas où A est soit Vérité, soit Mensonge, on peut observer 8 éventualités :
Et finalement, que l'on s'adresse à Vérité ou à Mensonge, on obtiendra les mêmes réponses :
Un « da » signifie alors que B est Hasard, on s'adressera donc à C lors des questions suivantes ; un « ja » nous amenera à parler à B, qui n'est pas Hasard.
La question 2 (Est-ce que « da » signifie « oui » si et seulement si Rome est en Italie ?) nous permet de connaître l'identité du Dieu à qui l'on s'adresse.
Puisque Rome est en Italie, la réponse est « oui » si « da » signifie « oui », et est « non » sinon. Vérité répondra donc « oui » (« da ») dans le premier cas, et « non » (« da ») dans l'autre cas : au final, Vérité répondra « da » quel que soit la sens de « da ». Mensonge, quant à lui, répondra toujours « ja ». Le cas où l'on s'adresserait à Hasard ayant été exclu lors de la question 1, cette deuxième question permet d'identifier le dieu à qui l'on parle.
Remarquons que l'ajout « Rome est en Italie » n'a aucun intérêt, et qu'on peut se contenter de demander "Est-ce que « da » signifie « oui »".
Enfin, la question 3 (Est-ce que « da » signifie « oui » si et seulement si A est Hasard ?) nous permet de statuer sur la réelle identité de A, et donc, des trois dieux. En admettant que l'on s'adresse à Vérité, une réponse « da » signifie que A est bien Hasard, et « ja » signifie que A n'est pas Hasard (et que donc, c'est Mensonge). Si on s'adresse à Mensonge, on a les interprétations contraires.
Variantes
Cette énigme de logique la plus difficile de tous les temps a longuement été analysée, si bien que plusieurs variantes de réponses ont été proposées.
Une première variante, observée en 2001 par Tim Roberts, est d'utiliser des questions s'inspirant de l'énigme des deux portes, c'est à dire, des questions de la forme :
Si je vous demandais Q, me répondriez-vous « da » ?
Si la réponse logique à la question embarquée Q est « oui », la réponse sera « da », que l'on s'adresse à Vérité ou à Mensonge ; sinon, la réponse sera « ja ». Ce "lemme de la question embarquée" a pour conséquence de simplifier grandement l'énigme, au point que cela revient à ignorer le fait que les dieux puisse mentir et qu'ils répondent dans une langue inconnue.
On peut alors reformuler les questions :
- Q1' (à A) : Si je vous demandais « B est-il Hasard » , me répondriez-vous « da » ?
- Q2' (à B « ja » à Q1', à C sinon) : Si je vous demandais « Êtes-vous Vérité » , me répondriez-vous « da » ?
- Q3' (au même qu'à Q2') : Si je vous demandais « A est-il Hasard » , me répondriez-vous « da » ?
Une autre variante, proposée par Brian & Landon Rabern, est de confronter les dieux au paradoxe logique du menteur (« Je mens »). Imaginons que l'on pose à A la question Q1'' suivante :
Si je vous demandais Q*, me répondriez-vous « da » ?
où Q* est la question :
« Est-ce que : [(Vous allez répondre « ja » à la question Q1'') et (B est Vérité)] ou (B est Mensonge) »
Trois réponses peuvent arriver :
- Si A répond « da », c'est que la réponse à Q* est oui. Donc soit B est Mensonge (ce qui est envisageable), soit B est vérité et A a répondu « ja » (ce qui serait paradoxal, donc impossible). Donc B est Mensonge.
- Si A répond « ja », c'est que la réponse à Q* est non. B est donc ni Mensonge, ni Vérité (car « Vous allez répondre « ja » la question Q1'' » est vrai). Donc B est Hasard.
- Si B est Vérité, alors la question Q* se ramène à la question paradoxale «Vous allez répondre « ja » à la question Q1''». La tête de A explose, et on en déduit que B est bien vérité.
En une seule question, on a pu déterminer l'identité de B. Un seconde question permet alors simplement de clarifier l'identité de A et C. Il reste alors une question en rab, que l'on pourra poser à Vérité afin d'avoir une réponse définitive à « P=NP ? », « l'hypothèse de Riemann est-elle indécidable ? » ou tout autre question existentielle.
Sources :
Georges Boolos, The Hardest Logic Puzzle Ever
Brian Rabern & Landon Rabern, A simple solution to the hardest logic puzzle ever
/http%3A%2F%2Fstorage.canalblog.com%2F30%2F48%2F210892%2F58009482_o.jpg)
/http%3A%2F%2Fstorage.canalblog.com%2F34%2F91%2F210892%2F43596708_o.png)
/https%3A%2F%2Fassets.over-blog.com%2Ft%2Fcedistic%2Fcamera.png)