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 ment toujours et Aléatoire répond au hasard soit la vérité soit le mensonge...

Votre tâche est de dévoiler les identités de A, B et C en ne posant uniquement que trois questions dont la réponse est vrai ou faux ; chaque question ne peut être posée qu'à un seul dieu. 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 ceux-ci correspondent. »
Bolos 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 racontant ou pas la vérité peut être considéré comme un choix décidé par un jet à pile ou face : si la pièce tombe sur face, il ne dira que la vérité ; si elle tombe sur pile, il ne dira que des mensonges.
Aléatoire répondra par da ou ja à toute question vrai-faux.

La réponse
La solution décrite ci-dessous (due à T.S.Roberts), 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 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 ? ». Selon que ce dieu est Vrai ou Faux, on en déduit si B est Aléatoire ou non puis on finit par élimination.