Last week, we asked you to solve 'The Hardest Logic Puzzle In The World." This week, we're asking you to do it again – with a brand new puzzle.

#### Image Credit: Tara Jacoby

**Sunday Puzzle #2: George Boolos' "Hardest Logic Puzzle Ever"**

## UPDATE: SOLUTION

Let me begin by stating the obvious: The notion that any puzzle could be the absolute, singular, "hardest" in the world is clearly ridiculous. Every problem-solver brings unique skills to bear on any puzzle she encounters, and those skills will be more well-suited to some problems that others. One puzzler's "Hardest Puzzle Ever" can therefore be another puzzler's walk in the park. When we called last week's puzzle (the solution to which appears below) "The Hardest Logic Puzzle In The World," it was in reference to a version of the puzzle referred to as such by XKCD's Randall Munroe. Munroe's a smart guy, and the puzzle is (at least for everyone I've ever spoken with about it), *very* challenging. It seemed appropriate to indulge in the superlative.

Needless to say, I received several e-mails last week from people claiming that the title of **World's Hardest Logic Puzzle** belongs not to 100 Green-Eyed Dragons, but a baffling problem invented by George Boolos. Boolos was a philosopher and a mathematical logician who taught at MIT. He was an early proponent and pioneer of provability logic, i.e. applying modal logic to the theory of mathematical proof. He was also an authority on the 19th-century German mathematician and philosopher Gottlob Frege. Boolos once delivered a public lecture explaining Gödel's second incompleteness theorem entirely in words of one syllable. He was also an expert on puzzles of all kinds, and in 1993 he reached the London Regional Final of The Times crossword competition. A smart guy, to put it mildly. In a 1996 issue of *The Harvard Review of Philosophy*, Boolos presented the following brainteaser under the title "The Hardest Logic Puzzle Ever":

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

yesandnoaredaandja, in some order. You do not know which word means which.

Boolos also provides the following guidelines:

- It could be that some god gets asked more than one question (and hence that some god is not asked any question at all).
- What the second question is, and to which god it is put, may depend on the answer to the first question. (And of course similarly for the third question.)
- Whether Random speaks truly or not should be thought of as depending on the flip of a coin hidden in his brain: if the coin comes down heads, he speaks truly; if tails, falsely.
- Random will answer 'da' or 'ja' when asked any yes-no question.

Normally, I would prefer to have solved the featured puzzle before posting it, so that I can help you, the readers, solve the problem without spoiling the solution outright. However, **While I have worked on it off-and-on for several days now, I have not yet solved Boolos' puzzle!**

I have therefore asked philosopher Brian Rabern to assist me in moderating comments ( look for him below – username "B. Rabern"). Rabern is a lecturer in philosophy at the University of Edinburgh, where he studies language, logic, and semantic information. He has also published solutions to (and alternative presentations of) Boolos' puzzle in the philosophy journal *Analysis**. *This makes him uniquely qualified to guide you (and me) through the puzzle-solving process.

We'll be back next week with a breakdown of the solution – and a new puzzle! And, as always, remember to e-mail me with puzzles you'd like to see featured in future installments!

### SOLUTION to Sunday Puzzle #1: 100 Green-Eyed Dragons

* The solution is that all 100 dragons turn into sparrows on the 100th midnight.*

Before we unpack this, let's consult our toolbox. Different puzzles require different tools to solve. The more puzzles one works on, the bigger one's box of tools grows. After a while, one starts seeing puzzles which, while not identical to puzzles one has solved in the past, can be worked through with strategies we've relied upon in the past. One of the most versatile tools in any puzzler's toolbox is that of restating the problem, and one of the most powerful ways to restate a problem is to simplify it. Many of the Sunday Puzzles featured on io9 will be made more manageable through simplification, and the case of the green-eyed dragons is no exception.

So how does one simplify the 100 Green-Eyed Dragons puzzle? By making it the 1 Green-Eyed Dragon Puzzle. If you tell a single green-eyed dragon that "at least one of you" has green eyes, that dragon would know instantly and unambiguously that she has green eyes. At midnight she would turn into a sparrow.

So let's imagine 2 green-eyed dragons staring at one another, after being informed by you that at least one of them has green eyes. Each would look upon the other and, seeing a set of green eyes, think the following: "Do I have green eyes? I don't know. But if I do not, then this other dragon, upon seeing my non-green eyes, will know instantly and unambiguously that he is the one with green eyes, and at midnight will turn into a sparrow." Each dragon sits and waits to see what the other does. When, at midnight, neither dragon transforms into a sparrow, each one knows instantly and unambiguously that the other dragon did not leave because it, too, saw a dragon with green eyes. And so, on the second night, each transforms into a sparrow at midnight.

Let's expand the problem to 3 green-eyed dragons. Following your announcement, each dragon thinks to itself that if it does not have green eyes, then the other two dragons will determine their eye color by the reasoning laid out in the 2 green-eyed dragon scenario presented above. In this case, all three dragons wait for the other two dragons to transform into sparrows on the second midnight. When this does not happen, each of the three dragons concludes instantly and unambiguously that it has green eyes. On the third midnight, all three transform into sparrows.

Through the process of induction, we conclude that any number of green-eyed dragons, N, will all turn into sparrows on the Nth midnight following your seemingly inconsequential observation.

This can be hard to wrap your head around at first. It's the kind of solution that's liable to come across as utterly impossible until you've convinced yourself of it by working through a few more levels of induction. Even knowing the solution, it's easy to find yourself on, say, a six-dragon scenario thinking "I made this work for five dragons, but at six it seems to fall apart":

## DISCUSSION

I figured out how to determine which of Da/Ja means Yes/No in one question. Still working on the latter two. The key to the first one, without spoiling it, is to phrase your initial question in such a way that will force all three gods to answer the same way (meaning Random will always match the answer given by Truth and False). It's like the two-paths-in-the-woods riddle with one liar and one truther, but you don't know which one it is. The Random answer makes no difference in this case.