[Sohcahtoa82]

The Blue Eyes puzzle was a tough one to wrap my head around until I shrank the problem much smaller.

Imagine there are only two people on the island, A and B. A has blue eyes, B has brown eyes. When the guru makes his announcement, A sees that B has brown eyes, and deduces that he himself has blue, and gets on the boat at midnight.

Now, imagine BOTH A and B had blue eyes. On day 1, neither of them get on because they don't know their own eye color. The second day, though, A thinks "If I had brown eyes, then B would seen them and figured out that he's the only one with blue eyes on day 1 and gotten on the boat, but he didn't. That means I have blue eyes as well." B thinks the same thing, and gets on the boat.

Try it with three people, A, B, and C, with A being the only blue eyed person. On day 1, A sees no blue eyes and figures out he's the only one with blue eyes and gets on the boat. Simple.

But what if A and B are blue, and C is brown? A and B both see 1 person with blue eyes, C sees 2 people with blue eyes. It's important to note that A and B both believe there's either 1 or 2 people with blue eyes, and C believes there's either 2 or 3 people with blue eyes. On day 1, A and B know there could be 2 people with blue eyes including themselves and don't get on the boat. C sees 2 people, and knows he could be a third, and doesn't get on the boat. On day 2, A notices B didn't get on the boat and knows that B also knows that C has brown eyes. The only logical conclusion is that B didn't get on the boat because he saw A's blue eyes. And so A gets on the boat because he knows he has blue eyes. Likewise, B sees that A didn't get on the boat, and knows that both of them know that C has brown eyes, and also concludes he has blue eyes. C knows how A and B concluded they had blue eyes (Remember that they're all perfect logicians!), and concludes he has brown eyes.

What if all three have blue eyes? For days 1 and 2, they all have the same logic as C did in the previous paragraph. They all know there's at least 2 people with blue eyes, and possibly 3.

Let's jump ahead a bit. 6 people, A through F, and A, B, and C have blue eyes. On day 3, A looks around and notices that B and C didn't leave. A knows that B and C know that D, E, and F all have brown eyes. But because A knows that if there were only two people with blue eyes (B and C), they would have figured it out on day 2. That means there MUST be three people with blue eyes, and since he knows B and C have blue and D, E, and F have brown, he's the only possibility for having blue eyes. B and C come to the same conclusions themselves, announce their blue eyes, and get on the boat at midnight.

No matter how many people there are and how many of them have blue eyes, if the actual number of people with blue eyes is N, then all the blue-eyed people know there's either N (They see all the people with blue eyes and and they themselves have blue eyes) or N-1 (They see all the blue eyes and they DON'T have blue eyes) blue eyed people, where N is the actual number of blue eyed people. The brown eyed people all know there's either N or N+1. On day N, all the people with blue eyes will have figured out that they have blue eyes and will get on the boat because if the number of blue eyes was N-1, then they would have gotten on the boat the previous night. Meanwhile, all the people with brown eyes will still be waiting because they don't know if the number is N or N+1.

[sorokod]

Why is the guru's announcement required in the case of 100 blue - 100 brown? What additional information was provided to the islanders?

[Sohcahtoa82]

That's the hard question to answer. The best I can explain is that the guru's announcement is necessary to create the base case for the induction.

Imagine the 4-person scenario with 2 blues and 2 browns. Is it common knowledge that blue-eyed people exist? You might think, "Of course, because each blue-eyed person can see 1 other blue eyed person!" But keep in mind that nobody knows their own eye color. Blue-eyed person A doesn't know their own eye color, so he doesn't know that blue-eyed person B can see A's blue eyes. If blue-eyed A believes he has brown eyes, then he knows that blue-eyed B won't see any blue eyes! The fact that blue-eyed people exist is not common knowledge!

Add third blue-eyed person C. You'd think the above paragraph falls apart, but it doesn't. C knows that A sees B's blue eyes, sure. But C doesn't know that B knows that A knows that C has blue eyes, because C doesn't know his eye color! The idea that there are at least two people with blue eyes is not actually common knowledge, because again, nobody knows their own eye color. In addition, the sentence "A knows that B knows that C knows there's at least 1 person with blue eyes" isn't actually true, though it may seem that way at first glance. For it to be true, A would have to assume that he has blue eyes, because he's the one doing the presumption. B knows that C knows there's at least 1 person with blue eyes because B knows that C sees A. But A doesn't know the previous statement because he doesn't see A, because it's himself!

It's certainly hard to wrap your head around. There's other explanations at http://forums.xkcd.com/viewtopic.php?t=80149

[sorokod]

Thanks for taking the time to write this up.

[chadcmulligan]

Thank you, I can go to sleep tonight now.