L'Énigme la plus difficile du monde

« 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].

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)

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.

• Casse-tête

• L'énigme des trois dieux (solution détaillée).