Imagine you have a conversation with three gods. One god always tells the truths. Another god always lies. The third god gives random answers. These gods can answer any of your question which admits a yes or no response. The problem is that you don’t know which god is lying, which tells the truths and which is random. Moreover, the gods answer in their own language, in which “yes” and “no” sounds like “da” and “ja”, but you don’t know the translation of these words. By asking as few questions as possible you have to find out which god is random, which god tells the truths and which god always lies.
Take your time to try to solve this problem. Then read on.
First of all, the problem says that we have to solve it using as few steps as possible. It appears that we can estimate the number of required questions even without knowing the questions themselves. We have three gods and three roles for them. The number of different combinations of roles is just a number of permutations of these roles, which is 3!=6. At the same time if you asked n yes/no questions, then you may distinguish between 2n different situations. We need 2n to be bigger than 6, which gives us that we need at least three questions to determine the roles of the gods.
So, what these three questions should be? This is a hard problem and we will solve it in several steps:
- We will first solve the problem in the assumption that there is no random god and that the gods answer in English.
- After this, we will assume that they answer “da” and “ja” instead of “yes” and “no”.
- Eventually, we will solve the initial problem with a random god.
Each of these steps is much easier to solve and I advise you to stop here and try to think about the problem again.
So, we have two gods. One is always lying and the other is always telling the truth. Let’s say that S is some statement and we want to learn truthfulness of it. It appears that we can do it by asking only one question to an arbitrary god. To understand how to formulate the question, consider first the following truth table:
| T | S | desired answer |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Here I denoted by T the fact that we talk to the god which tells the truths and by S, as above, the actual truthfulness of the statement which interests us. 0 means “false” and 1 means “true”. Example: if we talk to the god which tells the truths and the statement S is false, then it matches the third line of a table and the desired answer is “no” (denoted in the table as 0).
The problem is that in the first two rows instead of the desired answer we will get an inverted answer since we are talking to the lying god. But if we ask our question not about S, but about some other statement Q1, which has inverted truth values in the first two rows of a table, we will get the desired result:
| T | S | Q1 | answer we get |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 |
As you can see, in this case, if we ask a question about the truthfulness of Q1, we instead get the correct answer about the truthfulness of P. Q1 just means that both statements T and S are logically equivalent, so our question to a god may sound like this: “Could you tell me please, if either both statements ‘you always tell the truth’ and ‘S’“are true, or both of them are false?” You can do your calculation to make sure that the response to this question always matches to the truth value of S, no matter which god you ask this question.
The second problem requires just a slight extension of this approach and you may want to try to do it yourself before moving on.
So, now instead of “yes” and “no” we have responses “ja” and “da” with unknown meaning. We can make an assumption that “ja” means “yes” (I call this assumption A below) and extend our truth table the same way as we did before:
| T | A | S | Q1 | Q2 | answer we get |
| 0 | 0 | 0 | 1 | 0 | da |
| 0 | 0 | 1 | 0 | 1 | ja |
| 0 | 1 | 0 | 1 | 1 | da |
| 0 | 1 | 1 | 0 | 0 | ja |
| 1 | 0 | 0 | 0 | 1 | da |
| 1 | 0 | 1 | 1 | 0 | ja |
| 1 | 1 | 0 | 0 | 0 | da |
| 1 | 1 | 1 | 1 | 1 | ja |
Here Q1 has the same meaning as before and Q2 inverts the value of Q1 in case “ja” means “no”. This may be a little bit difficult to digest at first, but the idea here is quite simple. We assume that “ja” means “yes” and we want to hear the response “ja” if S is true. But if “ja” means “no”, we want a god to revert his response so he still answers “ja” in case of truth, and this is the purpose of Q2.
How to ask the question of the truthfulness of Q2? We can explain to the god how we build the table above and then ask for a value of Q2. The god knows the values of T, A, and S and so he knows what number we are interested in. Then he either tells us the truths or lies, using rules of his own language. You may evaluate different possibilities of the answer yourself and see that he will say “ja” if and only if S is true.
Another approach to ask the same question is to ask it in a more direct fashion by using Conjunctive Normal Form of logical statements, but I’ll skip this since it is fairly simple and you can understand how to do it from Wikipedia article.
The question could be formulated much easier. Let’s once again assume that the gods answer “yes” and “no”. How would a god respond to the question “What would you tell me, if I asked you about the truthfulness of S?” The god which tells the truths would give us the correct value of S, this is simple. But the god which lies will be tricked. Let’s assume that S is true. If you ask a question about S directly, the god which lies would answer “no”. But we are not asking about S, we are asking about the answer he would give, so the god will have to lie again and say “yes”, the value of S. The same logic applies if S is false.
It is easy to extend this approach to the case when the gods answer with “ja” and “da”. The question is the following: “Would you say ‘ja’ if I asked you about the truthfulness of S? You can work out the logic behind this question yourself.
There are two reasons why I presented two possible solutions for this problem. First of all, I was asked this question at a job interview and I was able to come up with a solution with truth tables myself, so I am particularly proud of it (although I didn’t get that job). Another reason is that it is interesting that the first solution was achieved using quite trivial formal logic, while the second one is based on a language play, which cannot be formalized by mathematical methods. This means that, for example, the first solution could be potentially found by Artificial Intelligence, but the second, short and elegant, couldn’t even be represented using the methods of AI available today. This is a fundamental limitation of all of the formal systems which mathematics and AI use in comparison to a “real” logic used by humans.
After solving the second subproblem, we know how to ask for any information from truth-telling or lying god using only a single question. We just have to eliminate the god which gives us totally random answers. I’ll present the questions as though we could ask them directly, but you have to keep in mind that these questions should be “translated” to a form which allows us to get a correct response. The next paragraph contains a solution to the entire problem and you know what to do.
Let’s say that we enumerated the gods as 1, 2, 3. We ask the first god: “Is the second god Random?”. If he answers “yes”, it may be the truth, or it may just mean that the first god gave us a random response. In both cases, we can conclude that the third god is not random and we can proceed to ask questions to him. If the response to the question is “no”, then we know for sure that the second god is not random. The rest is trivial.
In the solution presented above, we didn’t define what “random” actually is, but it can mean different things. This puzzle was initially published by George Boolos and the definition which he used assumed that the random god flips the coin before each answer and the result of this flipping defines if he tells the truth or lies.
At first sight, it may look like a valid definition for randomness, since to the question “Are all roses are red?” we may receive responses “yes” or “no” with equal probability. At the same time, to the question “What would you tell me if I asked you whether all the roses are red?” he would give the response “no”. He flips the coin to decide if he tells the truths, but in both cases, he got caught into the trap of our indirect question. “Yes” is impossible and he doesn’t look like random anymore. The solution I presented above works for a truly random god as well, but the fact that the definition of randomness with flipping a coin doesn’t make him truly random is remarkable.
The last bit. We assumed that even if we don’t know the meaning of the words “ja” and “da”, we at least know what possible responses might be. This is a lot of information already! What if we didn’t know even a single possible word in god’s language? It is easy to solve the problem in four steps. First, ask an arbitrary question to learn at least one word from god’s vocabulary. Then apply the strategy derived above. This straightforward solution is easy, but is it possible to solve the problem with fewer steps?
If one of the gods is truly random (without flipping a coin), then the solution in three steps is impossible. It is clear that the last question can be asked only to a non-random god. If you think about it for a bit, this observation is also quite remarkable: we cannot get any information by asking the last question to the random god, but asking a question to the random god the first question is actually giving us information on who is not random (we used this trick in our initial solution). This is quite difficult to explain without going into depths of theory, but a short story is that this happens because a randomized answer can only reduce uncertainty, but cannot give you precise information.
So we have to determine which god is not random by using only two questions. The first response is some word which we’ve never heard before, so it cannot give any information. It means that the second question cannot depend on the response to the first question. If you add to the mixture true randomness, it appears that even though we can get some information from these two responses, we cannot confidently eliminate a random god. Details, unfortunately, are quite complicated and I will skip it.
If the random god is defined by flipping a coin, the solution in three steps is possible. The first two questions are the following:
- First ask the first god: “Let’s consider English transliteration of words ‘yes’ and ‘no’ in your language. If I asked you whether you are random would you answer with a response which goes alphabetically first in the list of transliterations?”
- Then ask the second god: “Would you give me the same response to the same question which I just asked?”
I leave it as a nice exercise to understand how you can make sense out of responses to these two questions and how to complete the puzzle in this case.