The hardest logic puzzle ever is a riddle by the logicians Raymond Smullyan and John McCarthy that became famous in the 1990s.

Imagine there are three oracles called True, False, and Random. True always tells the truth, False always lies and Random randomly tells the truth or lies. Your task is to find out which oracle is which by asking them some yes/no questions. But there is an additional difficulty: the oracles will reply in their mystic language, either saying "DA" or "BAL" and you don't know which one of these words means yes and which one means no.

Surprisingly, three questions are enough to solve the riddle.

Before you start pondering this, here are three things that are important to know:

1. The random oracle will decide whether or not to lie or tell the truth by secretly tossing a coin.
2. You can ask any yes/no question to any oracle of your choice.
3. You do not have to ask all questions at once. In fact, you can make use of the previous answers to adapt your questions and choose the oracle that you ask them to.

If you are struggling to find the solution, don't despair. After all, it's called the hardest logic puzzle ever. Here is the general idea behind the solution. With the first question you identify an oracle X which is not Random. You then ask the two further questions of X. The second question identifies whether X is True or False, and the third question identifies the other two oracles.

If and only if

The solution makes use of the logical concept of if and only if, which works as follows: given two statements A and B, the statement A if and only if B is true whenever A and B are both true or both false, otherwise it is false. This means that the statement

2+2=4 if and only if the Moon is made of cheese

is false because one component is true and one is false. On the other hand the statement

2+2=5 if and only if the Moon is made of cheese

is true because both components are false. These examples don't quite chime with our intuitive interpretation of what "if and only if" might mean, but try not to worry about this. Just keep in mind the logical definition given above. (If and only if is the negation of something called XOR, which you can read about here.)

Starting simple

Now let's go back to our riddle and start with a simplification. Let's suppose that DA means "yes" and BAL means "no".

First suppose you have already asked the first question to some oracle, which has identified a different oracle X that isn't Random. Can you then think of a simple question that will reveal who X is? Afterwards, can you think of a simple question for X which will reveal who the other two oracles are?

If not, then here are the answers. To find out if X is True or False you simply ask a question to which you already know the answer, such as:

Is 2 plus 2 equal to 4?

To identify the other two oracles you can then ask X:

Is this oracle (pointing at the oracle you asked the first question) Random?

Since you know if X is True or False, you can determine whether the oracle you asked the first question is Random or not. By elimination you identify the third oracle as well.

The first question

Suppose again that DA means "yes" and BAL means "no" (we will take care about the language issue later on) and let us turn to the crucial first question, which is the most difficult one. Pick any oracle O and ask:

Are you True if and only if this oracle (where you point at one oracle P different from O) is Random?

Suppose the answer you get from O is "yes". If O is True, then the oracle P must be random. That's because the statement

O is True if and only if P is Random

is true whenever both components are true, or both components are false.

If the answer is "yes" and O is False, then the true answer should have been "no, the statement 'O is True if and only if P is Random' is false". Since the first part of the statement, "O is true" is false, the second part of the statement, "P is Random" must be true (from the definition of if and only if).

So whether O is True or False, an answer of "yes" tells us that P is Random, which means that the third oracle, call it Q, is not Random.

What does an answer of "yes" tell us if O is Random? Well, it doesn't tell us with certainty what P is, but that doesn't matter. In this case, because O is Random, the third oracle Q is definitely not Random.

In summary, then, an answer of "yes" tells us with certainty that the third oracle Q is not Random, no matter what O is.

What if O answers "no"? Then if O is True this implies that P is not Random. If O is False, then the true answer should have been "yes, the statement is true". Since the first part of the statement

O is True if and only if P is Random

is false in this case, this means that the second part "P is Random" is also false.

So whether O is True or False, an answer of "no" tells us that P is not Random.

What does an answer of "no" tell us if O is Random? Well, it tells us that P can't be Random, because O already is.

In summary, then, an answer of "no" tells us with certainty that P is not Random, no matter what O is.

In both cases, whether O answers "yes" or "no", we have identified one oracle as not being Random. If O answers "yes", then the third oracle Q is not Random. And if O answers "no", then the oracle P is not random. This identifies our non-Random oracle X from above. We can now proceed with the other two questions as described to solve the riddle. The diagram below illustrates the answers our three questions will give us.

Note that the role of the if and only if here was to get certainty from the answers of O without knowing whether O is True, False or Random.

DA and BAL

Now consider the original riddle, where you do not know the meaning of DA and BAL. Here we need to introduce another layer of if and only if, which will allow us to elicit the same information as we did before, without knowing which of DA and BAL means "yes" and which means "no". Namely, by adding "if and only if DA means yes" at the end of all the three questions it turns out that we can interpret the answer DA as a positive answer to the original question, and the answer BAL as a negative answer to the original question. In the next section we see an example of this, now we are going to state the general solution to the riddle.

You start by picking an oracle O and ask it, while pointing to another oracle P,

Are you True if and only if P is Random, if and only if DA means yes?

This statement is true whenever the two statements

Are you True if and only if P is Random

and

DA means yes

are both true or both false, otherwise it is false.

As before, this question will identify an oracle X, different from O, that is not Random.

Then you ask of X:

Is 2 plus 2 equal to 4 if and only if DA means yes?

This will tell you whether X is True or False. Finally you ask of X:

Is this oracle (pointing at the oracle O you asked the first question of) Random if and only if DA means yes?

As before, this will tell you whether O is Random or not, and since you already know what X is, it solves the riddle.

Really?

To convince you that this works, let's look at the last question. You already know at this point whether X is True or False. Let's assume X is True. You are asking X about O, the oracle you asked the first question of.

Suppose that X answers DA and that DA means "yes". Then O is Random. Now suppose that DA means "no". Then O is also Random. That's because in this case the statement

DA means yes

is false, so since X said DA, which means "no", the statement

O is Random

is true.

What if X says BAL and that BAL means "yes". Then O is not Random. That's because in this case the statement

DA means yes

is false, so since X said BAL, which means "yes", the statement

O is Random

must also be false.

Similarly, if BAL means "no" then O is also not Random. That's because in this case the statement

DA means yes

is true, so since X said BAL, which means "no", the statement

O is Random

must be false.

What we have just shown is that, if X is True, then an answer of DA tells us that O is Random and an answer of BAL tells us that O is not Random, even though we don't know what DA and BAL mean.

A very similar argument shows that when X is False, then an answer of DA means that O is not Random and an answer of BAL means that O is Random. In summary, we can work out whether O is Random or not from X's answer without knowing which of DAL and BAL means "yes" and which means "no".

It is also possible to show that the answer to the first question identifies an oracle X that is not Random and the answer to the second question identifies whether X is True of False, even though you don't know which of DAL and BAL means "yes" and which means "no". We will leave this to you as an exercise.

Another puzzle for you

In a TV show you are shown two envelopes. If you open the correct envelope you win a huge prize, while if you open the wrong one you win nothing. There are two people and you can ask one of them a yes/no question. One person will tell the truth and the other will lie (and you don't know who is the truth-teller and who is the liar). Which question can you ask in order to identify the envelopes?

You can see the solution here.

---

About the author

Antonella Perucca is Professor for Mathematics and its Didactics at the University of Luxembourg. She is a researcher in number theory and invents mathematical exhibits. To find out more, explore her webpage.