See also xkcd version, or on wikipedia. I found the original link on Damien Katz’s blog. Its difficult to me, because there is a widely accepted solution that I could not grasp for quite some time. The wikipedia link includes the solution. Read one of the others if you just want the problem.
Here is the puzzle, followed closely by the solution:
On an island, there are 100 people who have blue eyes, and the rest of the people have green eyes. If a person ever knows herself to have blue eyes, she must leave the island at dawn the next day. Each person can see every other persons’ eye color, there are no mirrors, and there is no discussion of eye color. At some point, an outsider comes to the island and makes the following public announcement, heard and understood by all people on the island: “at least one of you has blue eyes”. The problem: Assuming all persons on the island are truthful and completely logical, what is the eventual outcome?
The accepted solution is that all of 100 the blue eyed people leave the island after 100 days. The short, misunderstood explanation is that the outsider introduced some “common knowledge” that was not there before, which allowed all the blue-eyed people to deduce their eye color.
The proof uses induction, and goes like this. If there were only 1 blue-eyed person (n=1), then he would see that there are no other blue-eyed people, and deduce that he is the one person the outsider mentioned. We would leave the island. If there were 2 blue-eyed people (n=2), then they would both see the other and expect the other to leave on day 1. When neither leaves the island after 1 day, they will each realize that they must be the “other one” with blue eyes, and leave together on the day 2. Using induction, bla bla, 100 days later all blue-eyed people leave.
Lets look at that more closely.
The argument works for day 1. Fairly obvious. Blue eyed person sees no other blue eyes, so he knows he is the one and leaves.
The argument still works for day 2. At first it seems the 2nd blue-eyed person has no reason to assume he is the “other one”. But he knows that there is more than one (one would have left after 1 day), but he can only only see one (so he must be the other).
Consider a green-eyed person on day 2. He would also know that there is more than 1 blue-eyed person. But he can see 2 blue-eyed people, so he will do nothing. He will not know that he has green eyes – he will simply reserve his judgment until day 3.
Eventually day 100 comes (induction allows us to jump forward like that), and all blue eyed people are confronted with the inevitable truth, and they leave.
- The 1st day pronouncement that someone has blue eyes appears to add no new knowledge. This is true for everything except the simplest case of a single-blue eyed person. The pronouncement is a device to assist in the induction proof. Really, they would simply leave 100 days after they got there, no outsider pronouncement necessary. (That is just harder to explain/prove).
- In some versions of the puzzle, the person has to know their eyecolor to leave (the example above is limited to blue). In those versions, if all of them know there are only 2 eye colors, then on day 101, all green eyed people will leave too. They would leave earlier if there were > 1 of them and < 100, and then the blue eyed people would leave one day later.