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
You need to ask $O(log_2 N)$ questions of one individual.
Pick a random person and ask the person an obviously true question, e.g. "Is 1 = 1?". The person's answer determines if the person is a Liar or a Truth teller. Now proceed to ask the person the questions asked in a Binary Search algorithm. Negate the person's answer if the person is a Liar.