Explanation to the Solution to 'Blue Eyes'

Hidden in the xkcd.com domain is a logic puzzle called 'Blue Eyes'; I'll let you follow the link to read the actual puzzle.

Hidden in another location on xkcd.com is the solution to the puzzle; I'll let you follow the link to read that.

The problem is that Randall Munroe, the developer of this puzzle and solution, doesn't explain the answer quite as well as he might; he so much as admits that his explanations aren't as clear as they might be (though with Randall, it's possible this is deliberate, given the kind of humor he displays in the webcomic associated with the domain name).

Having recently puzzled through the thing myself, I'll endeavor to provide a scholarly recapitulation of the puzzle's underlying logic. (Note that, while the puzzle itself is copyrighted by Munroe, scholarly analysis of copyrighted texts is protected in the U.S. under copyright law, so I'm not worried about receiving a cease-and-desist order from a man in a black hat.)

(For those who might need it: SPOILER WARNING! I'm about to explain the solution to Munroe's puzzle in potentially excruciating detail, so don't say you weren't warned.)

There is an unstated presumption in the initial conditions of the puzzle: it's presumed that the Guru is telling the truth. Since this presumption is necessary for the puzzle to be solvable, it can probably remain unsaid, but I point it out to show that, as Munroe himself states, the answer to the puzzle is not to figure out that the question is a trick question. You really can deduce the given answer logically.

Munroe begins by demonstrating that for any number of people on the island, if they are all blue-eyed, then they'll all eventually realize this after a number of days have passed. My explanation of this proof:

Begin with the hypothetical that Munroe does: that there is only one person on the island. In this case, that person knows his eyes are blue, and thus leaves that very night.

If there are two people on the island, then presuming the Guru is telling the truth, there is either one blue-eyed person and one non-blue eyed person, or two blue-eyed people. If person #1 (he) looks at person #2 (she) and doesn't see blue eyes, then he knows his eyes are blue and he leaves that night; likewise if she looks at him and doesn't see blue eyes, she knows her eyes are blue and she leaves that night.

Here's the first key to understanding the puzzle: if he looks at her and sees blue eyes, but she doesn't leave on the first night, then he knows that she saw blue eyes and was expecting him to leave. She realizes the same thing, and thus they both realize they have blue eyes and leave together on the second night.

Move on to three people. If only one has blue eyes, we're back in the original situation; since we know that there's at least one blue-eyed person, if that person can't see another blue-eyed person, then he knows he has blue eyes and leaves the first night. If two of the three people have blue eyes, then two of the people will see one other blue-eyed person and find themselves in the same situation as the two blue-eyed people alone; if she doesn't leave the first night, then she sees a second blue-eyed person, but since he doesn't see a second blue-eyed person, he has to be that person. The same is true of his not leaving and what she can deduce from that.

This is actually the second key, but we'll come back to it.

If all three of the people (A, B, and C) are blue-eyed, then the situation goes like this: since I can already logically determine (from the argument above) that if I'm not blue-eyed, the blue-eyed people I see will leave when they realize they're all blue-eyed, if they don't leave on that day, then I'm also blue-eyed, and we all leave on the third day.

Thus, Munroe's explanation can be boiled down to a formula: if there are X people, all with blue eyes, they will realize it and leave on day X. It's an inductive proof, to a point, but inductive logic still qualifies as logic.

If you're scratching your head wondering how it is that the people who don't have blue eyes realize that they don't have blue eyes, well, now we get back to the second key: It doesn't matter how many people without blue eyes you put on the island.

Consider the situation where you have 101 people on the island, but only 1 has blue eyes. Since each non-blue eyed person can see one blue-eyed person, they don't know for sure that they don't yet have blue eyes. But the single blue-eyed person sees nobody else with blue eyes, realizes he's the only one with blue eyes, and departs on the first night. When he departs, everyone else realizes that they don't have blue eyes, because if any of them had, the guy wouldn't have known to leave. X is 1, and he leaves on Day 1.

The same is true for 100 non-blue-eyed people and two blue-eyed people. The two blue-eyed people will each expect the other to leave on day 1, but when they don't, they'll realize that they're both blue eyed and leave on day 2. Why? Because each of them can only see one other blue-eyed person, and if that person didn't leave on day 1, it can only mean that that person saw another blue-eyed person. X is 2, and they leave on Day 2.

The final thing you may be asking yourself is this: how do the non-blue-eyed people realize that they don't have blue eyes? Isn't it possible that one of them will believe that they do have blue eyes simply by mistake?

Actually, no, that will never happen. Let's use the original puzzle setup to explain why: 100 blue-eyed people and 100 brown-eyed people.

If you are blue-eyed, you'll see 99 other people with blue eyes. Based on the chain of logic listed above, you'll expect them all to leave on Day 99.

If you are brown-eyed, you'll see 100 other people with blue eyes. Again based on the chain of logic listed above, you'll expect them all to leave on Day 100.

If you see 99 blue-eyed people, but they don't all leave on Day 99, that means you also have blue eyes. Note that this is true for each of the 100 people with blue eyes -- none of them actually realizes that he or she has blue eyes until that day when the other blue-eyed people don't leave. You then know you have blue eyes and leave on Day 100, and everyone else who realized this with you leaves on Day 100 as well.

If you see 100 blue-eyed people, and they all leave on Day 100, then you realize you don't have blue eyes. If you did, they'd have all stayed and you'd have all realized you have blue eyes on Day 101.

Nobody on the island knows for certain whether or not they have blue eyes until the day they all leave together; remember, if any of them could have figured it out sooner, they'd have had to leave sooner -- the rules are that once you know your eye color, you have to leave.

Interestingly enough, and one reason it took me so long to get my head around the answer, is that the solution seems similar to what I call the False Execution Paradox:

You are convicted of a death sentence in an imaginary nation. Because of a quirk in the law of this nation, you cannot be legally executed unless the following conditions are met:

• You must be executed within one week of the sentence, and
• You cannot be executed if you know the day of your execution prior to noon on the day before your scheduled execution.

At first glance, the combination of conditions, specifically the second one, seems impossible to satisfy, because of the following logical argument. Say you're sentenced on a Sunday:

You cannot be executed on the following Sunday, because if they tell you prior to noon on Saturday that you'll be executed, they'll violate the second condition, but if they don't tell you before the end of the day on Friday, you'll know on Saturday morning that you're going to be executed on Sunday (it's the only day left) and thus violate the second condition.

By the same logic, once you know you can't be executed on Sunday, you also can't be executed on Saturday -- since you know you can't be executed on Sunday, if they don't tell you before noon on Thursday, you'll know then you'll be executed on Saturday, which again violates the second condition. But if they tell you Thursday that you'll be executed Saturday, that also violates the second condition.

You can work out a chain of logic that 'proves' that there is no day on which they can legally execute you, so you sit in your cell confident that you'll have to be released when, completely by surprise, they inform you on Tuesday afternoon that you'll be executed on Wednesday, fully satisfying both conditions and legally executing you. What went wrong?

I don't yet have an answer to that question, but I suspect that the distinction lies in the difference between the logically valid modus ponens logical argument structure:

If A then B.
A.
Therefore, B.

And the logically invalid argument known as 'denying the antecedent':

If A then B.
Not A.
Therefore, not B.

And, of course, it may not be a formal logic flaw at all; just an odd mapping error between natural language and the symbolism of formal logic.

Here's my problem: the False Execution puzzle depends on a chain of logic constructed arithmetically over a timespan, but it can be demonstrated that the logical chain constructed is invalid (or possibly valid but unsound) simply by proposing a valid execution scenario. Blue Eyes is also dependent on a logical chain constructed arithmetically over a timespan, but it is not nearly as obvious that a scenario can be constructed that proves that the logical chain is unsound. For small numbers of people, the chain can be shown to be perfectly valid and sound, and while there's no reason to suspect that the chain can't be extended indefinitely, the same would be thought to be true of the False Execution puzzle, until it's demonstrated how the chain can be broken.

If you think I'm a bit weird for staying up nights worrying over this stuff, then, well, you're right.