Sunday Puzzle #2: George Boolos’ “Hardest Logic Puzzle Ever”

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 yes and no are da and ja, 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.

Do not scroll down until you are ready for answer 🙂

http://io9.com/can-you-solve-the-worlds-other-hardest-logic-puzzle-1645422530

*******

SOLUTION:

Your first move is to find a god that you can be certain is not Random.

Question 1: Ask god B, “If I asked you ‘Is A Random?’, would you say ‘ja’?”. If B answers “ja,” either B is Random (and is answering randomly), or B is not Random and the answer indicates that A is indeed Random. Either way, C is not Random. If B answers “da,” either B is Random (and is answering randomly), or B is not Random and the answer indicates that A is not Random. Either way, you know that a particular god is not Random.

Now we know that we can talk to a non-random god. And given the embedding device it doesn’t matter whether we address a liar or truth-teller.

Question 2: Go to the god who was identified as not being Random by the previous question (either A or C), and ask him: “If I asked you ‘Are you False?’, would you say ‘ja’?”. Since he is not Random, an answer of “da” indicates that he is True and an answer of “ja” indicates that he is False. (Note that other questions would also work here, e.g. “Does Da mean yes?”; if “da,” then he is True, if “ja,” then he is False.)

Question 3: Ask the same god the question: “If I asked you ‘Is B Random?’, would you say ‘ja’?”. If the answer is “ja,” B is Random; if the answer is “da,” the god you have not yet spoken to is Random. The remaining god can, then, be identified by elimination.

Sunday Puzzle #1: 100 Green-Eyed Dragons

This has been around for a long time, and existed in various forms, but the version we’ll be solving was encountered in a handout given to physics students at Harvard, and is called “Green Eyed Dragons.”

You visit a remote desert island inhabited by one hundred very friendly dragons, all of whom have green eyes. They haven’t seen a human for many centuries and are very excited about your visit. They show you around their island and tell you all about their dragon way of life (dragons can talk, of course).

They seem to be quite normal, as far as dragons go, but then you find out something rather odd. They have a rule on the island which states that if a dragon ever finds out that he/she has green eyes, then at precisely midnight on the day of this discovery, he/she must relinquish all dragon powers and transform into a long-tailed sparrow. However, there are no mirrors on the island, and they never talk about eye color, so the dragons have been living in blissful ignorance throughout the ages.

Upon your departure, all the dragons get together to see you off, and in a tearful farewell you thank them for being such hospitable dragons. Then you decide to tell them something that they all already know (for each can see the colors of the eyes of the other dragons). You tell them all that at least one of them has green eyes. Then you leave, not thinking of the consequences (if any). Assuming that the dragons are (of course) infallibly logical, what happens?

If something interesting does happen, what exactly is the new information that you gave the dragons?

This is not a trick question. There’s no guessing or lying or discussion by or between dragons. The answer does not involve Mendelian genetics, or sign language. The answer is logical, and the dragons are perfectly logical beings. And no, the answer is not “no dragon transforms.”

Do not scroll down until you are ready for answer 🙂

http://io9.com/can-you-solve-the-hardest-logic-puzzle-in-the-world-1642492269?

*******

SOLUTION:

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.

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.

Consider the case N = 1. Here it is clear that you provided new information, since you essentially told the one dragon that he has green eyes. But for the cases N ≥ 2, the new information is slightly more subtle.

Consider the case N = 2. Prior to your announcement, A knows that B has green eyes, and B knows that A has green eyes. That is the extent of the knowledge, and they can’t conclude anything else from it. But after you tell them that at least one of them has green eyes, then A knows two things: He knows that B has green eyes, and he knows that B knows that there is at least one dragon with green eyes (because A knows that B heard your information). B gains a similar second piece of information. This second piece of information is critical, as we saw above in the reasoning for the N = 2 case.

Consider the case N = 3. A knows that B green eyes, and he also knows that B knows that there is at least one dragon with greens eyes (because A can see that B can see C). So the two bits of information in the N = 2 case above are already known before you speak. What new information is gained after you speak? Only after you speak is it true that A knows that B knows that C knows that there is at least one dragon with green eyes.

The analogous result holds for a general number N. There is no paradox here.Information is gained by your speaking. More information is added to the world than the information you gave. (For example, A knows that you made your statement while stepping onto your boat and wearing a blue shirt. Or, more relevantly, A knows that you made your statement in front of all the other dragons. In short, it’s not just what you say; it’s how you say it.) And it turns out, as seen in the proof of Claim 1, that the new information is indeed enough to allow all the dragons to eventually figure out their eye color.

To sum up: Before you make your announcement, the following statement is true for N dragons: A1 knows that A2 knows that A3 knows that . . . that A_N−2 knows that A_N−1knows that there is at least one dragon with green eyes. This is true because A_N−1 can see A_N ; and A_N−2 can see that A_N−1 can see A_N ; and so on, until lastly A1 can see that A2 can see that . . . that A_N−1 can see A_N . The same result holds, of course, for any group of N − 1 dragons. The point is that it is only after you make your announcement that the chain is extended the final step to the Nth dragon. The fact that the Nth dragon heard your statement is critical to the truth of this complete chain.

So, in the end, it turns out to be of great importance how far the chain, “A knows that B knows that C knows that . . .” goes. Note that if one of the dragons missed your farewell announcement (which was “At least one the 100 dragons on this island has green eyes”), then they will all happily remain dragons throughout the ages.