logic puzzle (truth-tellers / liars)

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.

• If there is a solution to this problem, it has to involve not always being able to figure out what "da" and "ja" mean within the allotted number of questions, which strikes me as mildly ludicrous, but I haven't figured out a way to prove it completely possible. If you were asked to figure out what "da" and "ja" mean on top of figuring out who's who, then there would be $2 \cdot 3! = 12$ possible answers that you need to be able to give, but only $2^3=8$ possible sequences of answers to the $3$ questions. – Dustan Levenstein May 12 '15 at 17:12
• The question is to find who is who you are not supposed to find what da and ja mean – vounoo May 12 '15 at 17:17
• Actually, I can prove it impossible: After asking your first question, every permutation of the three people remains possible, no matter how the first person responded (as a consequence of the fact that you don't know what "da" and "ja" mean). So there are 6 possible outcomes that you need to account for, but you only get $4$ remaining possible sequences of answers from the $3$ people. – Dustan Levenstein May 12 '15 at 17:19
• no. that is not true this puzzle has a solution – vounoo May 12 '15 at 17:21
• There is a typo in my first comment, btw; I meant to say "I haven't figured out a way to prove it completely impossible." What makes you say the puzzle has a solution? I just proved it impossible by a straightforward application of the pigeonhole principle. – Dustan Levenstein May 12 '15 at 17:22

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:

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):

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?

If $X$ is a question you wish to ask someone, then consider instead the question $$Q(X) := \text{Would you answer ja to the question }X\text{?}$$ Assuming they know the answer, the truth teller and the liar are both guaranteed to answer the truthful answer to $X$, according to the translation of "ja" meaning yes and "da" meaning no.

Let A, B, C be the three people. If we list, in order, the liar, the truth teller, and the randomizer, then the six possibilities are: ABC, ACB, BAC, BCA, CAB, CBA.

Start by asking person A $Q(X)$, where $X$ is the question "Is person B the randomizer?" If A answers "ja", then the possibilities are: ACB, CAB, BCA, CBA. If A answers "da", then the possibilities are: ABC, BAC, BCA, CBA. Either way, we have narrowed down someone we know is not the randomizer, respectively C and B. Now some choice values of $Q(X)$ to ask this other individual for the remaining two questions to narrow down everyone should be pretty clear.

This following alternative is quite elegant, but it has to assume that the truth teller and the liar will remain in silence if they do not know the question's answer:

(1) Decode the language

In order to know which of da and ja means yes and no, ask arbitrarily to any one of them an indirect question about as to whether a statement $\top$ is the case. Obviously, $\top$ should be a statement that you know that is true already, such as:

If I ask you if the Random is one of you would you say it is true?

Since it is an indirect question, and the truthfully answer to the innermost question is positive, the resulting answer, be it ja or da, will be yes - and so we decode the language.

(2) Find the Random

Assuming that the truth teller and the liar will remain in silence if they do not know how to answer a certain question, we can ask A:

If I ask you if B is the Random what would C say?

Then there are three possible answers here, namely, yes; no; silence.

It is easy to see that if A keeps in silence it is because C is the Random - A has no access to his random answer. Now let A say:

• Yes: Then, since C is not the Random we have two possibilities, that is, either A is the Random or B is the Random. If the latter, then we fall into a contradiction - either C being the False or being the True is inconsistent with the fact A answered yes (show it!). Then A is the Random.

• No: Again, because C is not the Random we have two possibilities, namely, either A is the Random or B is the Random. If the former, then, again, either C being the False or being the True is inconsistent with the fact A answered no (show it!). Then B is the Random.

(3) Find the Truth and False teller

Now that we know that $X$ is the Random we can arbitrarily ask to one of the other two:

Is $X$ the Random?

If he says the corresponding word for yes, he is a Truth teller and the other a False teller. If not, he is a False teller and the other a Truth teller.

I believe however that the step (1) is superfluous, since we can use the procedure suggested in my answer above in (2) and (3) instead. This, therefore, suggests that this puzzle can be minimized to a two-questions solution.

• Silence is not a possibility if he cant answer he will just say something random – vounoo May 13 '15 at 22:23
• @vouno This is why I said it depends on this silence assumption :) – Bruno Bentzen May 14 '15 at 2:53
• If silence assumption does not hold you can do it in two question – vounoo May 14 '15 at 19:10