His fame is not exaggerated. It brings together three different difficulties in a single knot—truth, lies, and unknown language—and demands a solution that neutralizes them at the same time.
The most difficult logic puzzle in the world
Riddle statement
Three gods, A, B and C, are called Truth, Falsehood and Random, in some order.
- Truth always answers with the truth.
- Falsehood always responds with a lie.
- Random answers at random.
They understand your language, but they answer using the words “da” and “ja”, and you don't know which means “yes” and which means “no”.
You can ask exactly three questions, each directed at a single god and with a yes/no answer.
How do you identify with certainty which is which?
Show solution
Solution
Answer: the three gods can be identified in exactly three questions.
The key is to use one control question very carefully. For any proposition $P$, define:
$M(P)$: "If I asked you whether $P$, and you answered 'da', would you be telling the truth?"
This question does not simply tell us whether $P$ is true. It does something subtler and more useful.
What $M(P)$ really means
If we ask $M(P)$ to Truth:
- he answers da if $P$ is true;
- he answers ja if $P$ is false.
If we ask $M(P)$ to Falsehood:
- he answers da if $P$ is false;
- he answers ja if $P$ is true.
This does not depend on whether da means yes or no. In both possible languages, the pattern is the same.
So, for any god who is not Random:
| God asked | $P$ true | $P$ false |
|---|---|---|
| Truth | da | ja |
| Falsehood | ja | da |
In other words:
$M(P)$ answers da exactly when $P$ matches the fact that the god asked is Truth.
That is the useful tool. It does not erase the liar; it uses him.
How to turn it into a reliable question
If we want to know any proposition $Q$, we do not ask $M(Q)$.
We ask:
$C(Q)$: "If I asked you whether $Q$ if and only if you are Truth, and you answered 'da', would you be telling the truth?"
Why does this work?
- If the god is Truth, the inner proposition "$Q$ if and only if you are Truth" is equivalent to $Q$.
- If the god is Falsehood, the inner proposition is equivalent to "not $Q$". But Falsehood answers da precisely when the inner proposition is false. So he again answers da when $Q$ is true.
Therefore, for any non-random god:
| Question $C(Q)$ | $Q$ true | $Q$ false |
|---|---|---|
| Answer | da | ja |
Now da has become a reliable signal about $Q$, even though we still do not know what da means and we still do not know whether the speaker is Truth or Falsehood.
First question: secure a non-random god
Ask A:
"If I asked you whether B is Random if and only if you are Truth, and you answered 'da', would you be telling the truth?"
That is, ask A the form $C(B\text{ is Random})$.
Act as follows:
- if A answers da, ask the second question to C;
- if A answers ja, ask the second question to B.
Why does this work?
If A is not Random, the answer to $C(B\text{ is Random})$ is reliable:
- da means B is Random, so C is not;
- ja means B is not Random, so B is safe.
If A is Random, the answer may be anything. But then B and C are both non-random, so either choice is safe.
In every case, after the first question you have selected a non-random god. Call him $Y$.
Second question: locate Random
Ask $Y$:
"If I asked you whether A is Random if and only if you are Truth, and you answered 'da', would you be telling the truth?"
That is, ask $C(A\text{ is Random})$.
Since $Y$ is not Random, the answer is reliable:
- if he answers da, A is Random;
- if he answers ja, A is not Random.
If A is not Random, then Random is the third god: the one who is neither A nor $Y$.
Now Random has been identified.
Third question: distinguish Truth from Falsehood
The two remaining gods are non-random. Choose one of them, call him $X$.
Ask him $M(P)$ with a proposition you know is true, for example:
"If I asked you whether two plus two is four, and you answered 'da', would you be telling the truth?"
Here $P$ is true.
From the first table:
- if $X$ answers da, $X$ is Truth;
- if $X$ answers ja, $X$ is Falsehood.
The last god is identified by elimination.
Thus Truth, Falsehood and Random are identified in exactly three questions.