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?
Best Answer
This is known as Ulam's problem of searching with lies. For one lie it was first solved by Andrzej Pelc. The minimum number of questions is not hard to calculate but the strategy attaining this number in the worst case takes several pages to describe. Later the solution was simplified.
For $n$ objects with $1$ lie, $n$ even, the number $q$ of questions needed is the smallest solution to $\frac{2^q}{q+1} \geq n$ which is $14$ when $n=1000$. There is a non-adaptive solution using Hamming codes that uses at most one more question than Pelc's method, but can specify all the questions before gameplay begins.