[Math] logic puzzle (truth-tellers / liars)

logicpuzzle

I am trying to solve this puzzle. It is supposed to be solvable.

There are 3 people A,B,C. One of them is always lying, one of them is always telling the truth and one of them is always answering randomly. You can address one person at a time. They understand your language but they will always answer you in their own language with "da" or "ja" which mean yes and no but you don't know which is which. You must find who is who in 3 questions.

They know who is who amongst them, and if the truth teller or false teller doesnt know if he is lying or not (ie if you ask something that he cant possibly know so he can lie or say the truth) he answers randomly.

This is supposed to be solvable as I mentioned earlier. Any help would be appreciated.

Best Answer

This is famously called by George Boolos the "Hardest logic puzzle ever" (1996).

He, that, as far as I know, was the first to present and solve it, states the puzzle as follows:

Three gods A, B, and C are called, in no particular order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for yes and no are da and ja, in some order. You do not know which word means which.

Some hints:

Since either A, B or C is the True, False and Random, we have $3!=6$ possible cases.

Now consider those three questions:

  • Is A the Random or B is the False? ($Q_1$)
  • Is B the Random or C is the False? ($Q_2$)
  • Is C the Random or A is the False? ($Q_3$)

You should ask them to no matter who, in the structure:

If I asked you Q, would you answer me yes?

Note that the above indirect sentence contains two questions one inside another. The result is that even if the False lies in the innermost question, he will have to lie about lying in the out-most question and this amounts to the cancelling of the negations.

In a normal scenario, that is, where the foreign language problem is not put, then those three questions are enough to find out the identity of A, B, C.

To see this, simply construct a truth table of $2^3=8$ lines, corresponding to the possible combinations of answer to those questions: $$\begin{array} {|c|} \hline Q_1 & Q_2 & Q_3 & Interpretation\\ \hline \color{red}{1} & \color{red}{1} & \color{red}{1} & --\\ \hline 1 & 1 & 0 & \text{A: Random, B: True, C: False} \\ \hline 1 & 0 & 1 & \text{A: True, B: False, C: Random}\\ \hline 1 & 0 & 0 & \text{A: Random, B: False, C: True}\\ \hline 0 & 1 & 1 & \text{A: False, B: Random, C: True}\\ \hline 0 & 1 & 0 & \text{A: True, B: Random, C: False}\\ \hline 0 & 0 & 1 & \text{A: False, B: True, C: Random}\\ \hline \color{red}{0} & \color{red}{0} & \color{red}{0} & -- \\ \hline \end{array}$$

Where:

$$Q_1 \equiv Random(A) \vee False(B)$$ $$Q_2 \equiv Random(B) \vee False(C)$$ $$Q_3 \equiv Random(C) \vee False(A)$$

Indeed, since there is one and only one True, False and Random, it is easy to see that the first and last lines of the table are impossible (show it!). Hence, of of it amounts to, again, 6 possible interpretations, where in every case we can find the True, False and Random's identity.

The above solution assumes we know the language of the True, False and Random.

Now, in its own language variation, we can try to overcome the fact we don't know what ja or da means by considering the following question, as firstly observed by Roberts (2001):

If I asked you Q, would you answer me ja?

In fact, this answer to this question will come out as ja if the truthful answer to Q is yes, and as da if the truthful answer to Q is no. Now, what about applying this reasoning with the above solution?

Related Question