L'Énigme la plus difficile du monde

« L'Énigme la plus difficile du monde » est à l'origine un article publié par George Boolos, philosophe et logicien américain, dans le quotidien La Repubblica, sous le titre italien L'indovinello più difficile del mondo (republié en anglais sous le titre The Hardest Logic puzzle ever). Cette énigme lui a été inspirée par Raymond Smullyan.

É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[1] :

  • 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[2].

Origines

Boolos attribue au logicien Raymond Smullyan l'initiateur de l'énigme et à John McCarthy la difficulté supplémentaire des réponses de sens inconnu.

Des énigmes similaires se trouvent dans les publications de Smullyan, comme par exemple dans What is the Name of This Book? (p. 149-156), où il décrit une île haïtienne dont la moitié des habitants sont des zombies (qui mentent toujours) et l'autre sont des humains (qui ne mentent pas) et il explique :

« La situation est extrêmement compliquée par le fait qu'ils comprennent tous parfaitement l'anglais mais qu'un antique tabou leur interdit de prononcer des mots dans une autre langue que leur langue indigène. Même si vous n'attendez qu'une simple réponse par oui ou par non à vos questions, ils vous répondront par “Bal” ou “Da” mais on n'a jamais su lequel correspondait à oui ou à non. »

D'autres énigmes sont relatées dans The Riddle of Sheherazade (en français, les Devinettes de Shéhérazade)

Solution

La solution décrite ci-dessous, due à T.S.Roberts[3], utilise le résultat préliminaire suivant : pour toute question Q admettant seulement les réponses « oui » ou « non », poser à Vrai ou à Faux la question « Si je vous demandais Q, répondriez-vous ja ? » a pour réponse ja si la réponse correcte à Q est « oui », et pour réponse da sinon (ce résultat, que les auteurs appellent le lemme de la question incluse, se démontre aisément en étudiant les huit cas possibles). On en déduit alors le protocole suivant :

Étape 1 : Demander à B, « Si je vous demandais “Est-ce que A est Aléatoire”, répondriez-vous ja ? ». Si B répond ja, alors ou B est Aléatoire (et a répondu au hasard), ou B n'est pas Aléatoire, et sa réponse indique que A l'est ; dans les deux cas, C n'est pas aléatoire. Si B répond da, alors ou B est Aléatoire, ou sa réponse indique que A n'est pas Aléatoire ; dans les deux cas, A n'est pas Aléatoire.

Étape 2 : Demander au dieu identifié comme non aléatoire à l'étape 1 (A ou C) : « Si je vous demandais “Êtes-vous Vrai”, répondriez-vous ja ? ». Comme il n'est pas Aléatoire, s'il répond ja, il est Vrai et sinon il est Faux.

Étape 3 : Demander au même dieu : « Si je vous demandais “Est-ce que B est Aléatoire ?”, répondriez-vous ja ? ». On en déduit si B est Aléatoire ou non puis on finit par élimination.

Notes et références
  1. George Boolos, « The Hardest Logic Puzzle Ever » in Harvard Review of Philosophy 6 (1996) p. 62-65
  2. Dans la version de Boolos, Aléatoire se comporte au hasard comme Vrai ou comme Faux, mais cette formulation permet une solution beaucoup plus simple au puzzle ; cette remarque a été faite par Brian Rabern et Landon Rabern dans (en)A simple solution to the hardest logic puzzle ever, (Analysis 68 (298), 105–112, April 2008), article dans lequel ils analysent les possibilités offertes par la formulation de Boolos, et suggèrent la modification donnée ici.
  3. T.S. Roberts, Some thoughts about the hardest logic puzzle ever (Journal of Philosophical Logic 30:609–612(4), décembre 2001

Articles connexes

Liens externes
  • Portail des mathématiques
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.