A brief meditation on formal systems and lying goblins

The other day I came across some people on The Internet talking about a certain scene from Labyrinth, which is a movie from the 80s (if you haven't seen it you should - lavish musical numbers, very unsettling Jim Henson puppetry, David Bowie doing contact juggling in spandex, it's really got it all!)

The scene plays out like so (lightly edited by me):

Goblin 1: The only way out of here is to try one of these doors.


Goblin 2: One of them leads to the castle at the center of the labyrinth, and the other one leads to (bum bum bum bum!) certain death!


Both Goblins: Ooooooo!


Sarah: Which one is which?


Goblin 1: Erm...we can't tell you.


Sarah: Why not?


Goblin 2: You can only ask one of us. It's in the rules! And I should warn you that one of us always tells the truth and one of us always lies. That's a rule too. (Points to other goblin) He always lies.


Goblin 1: I do not! I tell the truth!


Goblin 2: Oh, what a lie!


(Both goblins chortle)

This is a classic riddle, perhaps the most famous example of a type of logic puzzle known as Knights and Knaves. (It isn't made clear in the movie, but you can only ask one of the goblins one question, and they can only answer with a yes or a no. From that single yes/no you must deduce which door is the correct one. You can also assume that both goblins are telling the truth right up until the moment they stop explaining the rules.)

People were puzzling a bit over this one - the rules are simple, but the solution can seem a little complicated, especially if you haven't seen it before. I wanted to post about it because I think this is a case where a formal approach can be a lot more straightforward then working through the problem in plain English. To that end, let's model this problem using boolean algebra!

If you've done a lot of programming you've almost certainly worked with boolean algebra before - it's all the stuff you do with true, false, &&, ||, etc. More precisely, boolean algebra is a formal system devised by George Boole in 1847. It has two values, \(true\) and \(false\), and uses the standard logical connectives, \(and\) (usually written as \(\land\)), \(or\) (usually written as \(\lor\)), and so on.

Let's take a stab at modeling the problem with this algebra. We have one input - the question we ask (and, technically, the goblin we ask it of, but since both goblins are equally likely to be the liar asking one instead of the other doesn't change anything). We have one output - the goblin's answer. Finally, we have two unknowns - the goblin that's lying, and the door that leads to the castle. How do we express the output in terms of the other three variables?

If the goblin is telling the truth, he will answer the question correctly. If he's a liar, he will "flip" the answer. Let's let \(A\) represent the answer we get back from the goblin, \(Q\) represent the correct answer to the question we asked, and \(G\) represent the "lyingness" of the goblin (i.e. true if the goblin's the liar, false otherwise.) The possible inputs and outputs look like this:

Stare at this table long enough and you may notice that \(A\) is true if and only if \(G\) and \(Q\) are not equal. Those of you familiar with boolean algebra have already concluded that we can get the value of \(A\) by combining \(G\) and \(Q\) using the \(xor\) ("exclusive or ") operator, which is indeed true if and only if its arguments are different:

$$A = G \oplus Q$$

Now we have \(A\) in terms of \(G\) and \(Q\). But what of the doors? Well, we don't have any restrictions on the types of questions we can ask, and it's pretty obvious from the problem statement that we need to pick a question such that the goblin's response will tell us which door to choose (we could easily deduce which goblin is the liar by asking a question which is obviously true - but that doesn't tell us anything about the doors!)

(You may have noticed that since we can ask any question, we can ask questions that are boolean combinations of other questions - for example, "Is it Wednesday and does the sun orbit the earth?" Pocket this observation for now; we'll come back to it later!)

Either the left door is correct, or the right one is, and the answer to our question has to somehow tell us which is which. So we know that, whatever question we end up asking, it has to depend on the state of the doors somehow - which means it's a question we don't already know the answer to. We'll replace \(Q\) with \(Q_D\) from now on to reflect that fact (and, for future reference, we'll say \(D_L\) and \(D_R\) are true if the left and right doors lead to the castle, respectively.)

Now we have both of our unknowns covered - \(G\) represents whether the goblin we're talking to is a liar, and \(Q_D\) tells us which door we should choose. Let's take another look at that truth table:

Are we any closer to solving the problem? Not really, but looking at the table it should now be clear why - we want to go backwards, starting with \(A\) and deriving \(Q_D\). But we can't do that because we have two degrees of freedom - we don't know if the goblin is a liar, and we don't know what the truthful answer to \(Q_D\) would be. What we need to do - by picking the right question - is to take

$$A = G \oplus Q_D$$

and either eliminate \(G\) altogether (probably not possible) or somehow turn it into a constant.

At this point you should try engaging in the sacred mathematical tradition of Messing Around. Contemplate the problem statement; take note of all the things you know for sure and the things you still need to figure out (make a list if it helps!) You should also try playing with the algebra a bit. Don't focus too much on driving to a solution, just kick around some expressions and see what falls out. Spend a few minutes on this and see if you can guess where we're going (or if you already know the answer, read on!)

Two important things you may have realized:

• We know for a fact that exactly one goblin is a liar. Can't be two, can't be zero.
• \(xor\) is commutative, i.e. \(true \oplus false = false \oplus true = true\)

Taken together, these imply that, if we use \(G_1\) and \(G_2\) to stand for the lyingness of the two goblins, \(G_1 \oplus G_2\) is always true! This is a very useful fact, but to leverage it we have to find a way to get both \(G\)s into our earlier expression. The most straightforward way to do this is to ask about the other goblin directly: i.e. "is the other goblin the liar?" But wait - is that even allowed? Well, yes! The problem statement doesn't mention it explicitly, but neither does it forbid it (incidentally, when solving the problem verbally the "trick" is realizing you need to ask this sort of question - hopefully this is more obvious when thinking through things algebraically!)

Asking about the other goblin directly simply substitutes \(G_2\) for \(Q_D\), which gives us \(G_1 \oplus G_2\) (notice that no matter which goblin we pose this question to, the answer will always be yes.) But \(Q_D\) has to depend somehow on the state of the doors, so let's find a way to get \(D_L\) back into the mix. As we mentioned earlier, our question can be a boolean combination of other questions, so we can substitute \(Q_D\) with \(G_2\) and \(D_L\), joined together with a boolean conjunction (to keep things consistent, let's stick to \(xor\).) After performing our substitution, we end up with:

$$A = G_1 \oplus (G_2 \oplus D_L)$$

For our last step, we'll use the associative property of \(xor\). This basically says you can move the parentheses around between \(xor\)s, like so:

$$A = G_1 \oplus (G_2 \oplus D_L) = (G_1 \oplus G_2) \oplus D_L = true \oplus D_L$$

We made it! We can solve the riddle by asking the first goblin \(G_2 \oplus D_L\) and inverting the answer. That will tell us whether the left door is the correct one (since \(true \oplus x\) is true iff \(x = false\).)

Since goblins aren't experts in boolean algebra, we should probably find a way to phrase our question in plain English. We could do this the brute-force way ("is exactly one of the following true: the other goblin is the liar, the left door is the correct one?") but you may have noticed that \(G_2 \oplus D_L\) is the form \(A\) would take if we asked the second goblin about the left door. Now we're ready to see the rest of the goblin scene:

Sarah: (To goblin 1) Would he (pointing to goblin 2) tell me that this door leads to the castle?

Goblin 1: Uh...(confers with other goblin)...yes?

Sarah: Then the other door leads to the castle, and this door leads to certain death!

Both Goblins: Oooooo!

Goblin 1: How do you know? He could be telling the truth!

Sarah: But then you wouldn't be, so if you told me he'd say yes, I know the answer is no.

Goblin 1: But I could be telling the truth!

Sarah: Then he would be lying, so if you told me he said yes I know the answer would still be no.

Goblin 1: Wait a minute...(to the other goblin) is that right?

Goblin 2: I don't know, I've never understood it!

(Both goblins chortle)

You may have noticed that in this post we almost exclusively talked about symbols and the rules for manipulating them. There was little discussion as to the broader "nature" of the problem vis-a-vis the real world, and we ended up unlocking the solution by noticing a few key properties of the \(xor\) operator (as opposed to talking through hypotheticals, as Sarah did.) I personally like the symbolic approach better because (in my opinion!) it keeps every step very small and easy to follow. I also think the trick behind the proof is a little more obvious when you restate the problem in formal terms.

I have this experience often when doing mathematics: the particulars fall away and I'm left thinking only about the symbols themselves and what I need to do with them. This strategy of "trusting the formalism" can be a very effective problem solving technique - indeed, I think formal systems are powerful and useful precisely because you can outsource your reasoning to them when working through a complex problem. It personally helped me understand formal systems better when I started seeing them as "reasoning tools" in this way.

Food for thought!

If you enjoyed this post, Terry Tao has a similar but much more sophisticated pair of articles on the blue-eyed islanders logic puzzle. It's a great puzzle, and very mind-bendy - even after you know the solution, it's hard to convince yourself that it is, in fact, a solution!

P.S. Using the same line of reasoning we just went through, you can in fact derive another solution to this puzzle. Can you figure out what it is?