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"
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 MIT philosopher and logical mathematician George Boolos. Boolos, also a remarkably smart guy, was one of the founders of the field of probabilistic logic. In a 1996 issue of The Harvard Review of Philosophy , Boolos presented this 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.
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":
@rtg0nzalez @io9 i think the solution doesn't work if there's six or more dragons. someone needs to tell me why i'm wrong or i'll go bananas
— Jonathan A (@RecajBK) October 6, 2014
Part of this is because you're thinking about what Dragon A is thinking about what Dragon B is thinking about what Dragon C is thinking about what Dragon D is thinking about ... and so on, and it's easy to lose track. We are not, after all, computers, and we are not idealized logicians.
This is also why a situation like the one in the puzzle as this would almost certainly never play out in real life; there is simply no conceivable scenario in which 100 (non-computational) beings could trust one another to be perfectly and infallibly logical. Daniel Leivant – a professor of computer science and adjunct professor of mathematics and philosophy at Indiana University Bloomington – illustrates the impossibility of perfect logic AND perfect confidence in others' logic in a presentation delivered at 1994's International Workshop for Logic and Computational Complexity. In his presentation, Leivant describes a version of 100 Green-Eyed Dragons called "The puzzle of the muddy children" (for all intents and purposes, an identical puzzle to 100 Green-Eyed Dragons and Munroe's 'Blue-Eyes'):
What if my forehead is in fact clean, and the failure of the child before me to realize that his forehead is dirty is merely due to a weak reasoning capacity? In that case I should not assert that my forehead is dirty. Thus my being able to make the right inference about my forehead depends on my trusting the reasoning ability of the child before me, and his depends in turn on his trusting the children before him. Also, perhaps he said "I don't know if my forehead is dirty," not because he lacked the capacity to make the right inference, but doubted the capacity of the child before him. So the logical approach not only requires each child to be a perfect reasoner, but requires each child to assume that others are too.
Again, this can be tough to wrap your head around, but it can be demonstrated mathematically, programmatically, and by pure, blunt, step-by-step, pen-and-paper induction. The logic holds fast.
Finally: What new information was added when you said "at least one of you has green eyes"? For the answer, we turn to the answer provided for the Green-Eyed Dragons puzzle as I first heard it:
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 AN−2 knows that AN−1 knows that there is at least one dragon with green eyes. This is true because AN−1 can see AN ; and AN−2 can see that AN−1 can see AN ; and so on, until lastly A1 can see that A2 can see that . . . that AN−1 can see AN . 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.
In other words, your seemingly obvious statement ruined everything. As IanThomasHealy put it, in my new all-time favorite alternative solution to this puzzle:
"Logically, the dragons decide that the whole green-eyes thing is complete bunk, and choose to go find the d****-canoe who told them in the first place":
Previous Weeks' Puzzles
from Gizmodo http://ift.tt/1yqHW4K
via http://ift.tt/1yqHW4K
Blogger Comment