The answer is that the 100 blue-eyed people will leave the island on the 100th day.
The way to understand this answer is to first work through a much simpler version of the problem where there is only one-blue eyed person and one brown-eyed person on the island. Let's first try to solve it before the outsider arrives. The blue-eyed person doesn't see anyone with blue eyes, while the brown-eyed person sees one person with blue eyes. Since the blue-eyed person doesn't know whether there are any blue-eyed people on the island, he doesn't know whether he himself has blue eyes. So he will not leave the island.
However once the outsider informs the people that there is at least one blue-eyed person, the single blue-eyed person immediately knows that it must be him. Thus he leaves the island that night. Conversely, when the outsider makes her statement, the brown-eyed person doesn't yet know the color of his own eyes because he can already see someone with blue eyes. But he knows that if he does have brown eyes, then the other person will deduce their own blue eyes and leave the island that night. Or if he himself has blue eyes, then the other person will similarly not yet know the color of his eyes and will stay on the island. Once he observes the blue-eyed person leave the island that night, he then immediately knows that he himself has brown eyes.
So in this simple case, at least, the outsider's statement conveyed crucial information to the blue-eyed person that he didn't previously know and that made the difference to whether he left the island or not. Also, on observing the blue-eyed person leave the island, the brown-eyed person deduces that he himself has brown eyes.
Now consider the next simplest case where there are only two blue-eyed people and two brown-eyed people. Again, let's try to solve it before the outsider arrives. Each blue-eyed person can see one other blue-eyed person, while the brown-eyed people can see two people with blue eyes. Therefore everyone knows that there is at least one blue-eyed person on the island.
The first blue-eyed person realizes that if he himself has brown eyes then his scenario is identical to the single blue-eyed person scenario that we just analyzed. However, without the outsider's information, the other blue-eyed person cannot deduce that he has blue eyes and will therefore stay on the island. He similarly realizes that if he has blue eyes, he has no way of knowing this, so will stay on the island.
However when the outsider states that there is at least one blue-eyed person, the first blue-eyed person will now reason differently. He again realizes that if he has brown eyes then his scenario is identical to the single blue-eyed person scenario that we just analyzed. But he now knows that the other blue-eyed person would deduce that he himself has blue eyes and leave the island on the first night. So the first blue-eyed person now just has to wait until that night to see if the other blue-eyed person leaves the island. If he does, then he can deduce that he himself has brown eyes. If he does not leave, then he can deduce that he himself has blue eyes, and will leave on the second night. The other blue-eyed person reasons in the same way and also leaves on the second night. The brown-eyed person also reasons in a similar way. However, because he can see two blue-eyed people, he will wait until the second night to see what happens. When he observes the blue-eyed people leave the island on the second night, he then immediately knows that he himself has brown eyes.
So the outsider's statement, which only seemed crucial in the one blue-eyed person scenario was also crucial in the two blue-eyed people scenario. That's because it allowed each blue-eyed person to rule out the one-blue-eyed person scenario by observing what happened after the first night. It also allowed each brown-eyed person to confirm the two blue-eyed people scenario after the second night.
The same line of reasoning applies to the three blue-eyed people scenario. Without the outsider's statement, no-one will leave the island. With the outsider's statement the three blue-eyed people can rule out the two blue-eyed people scenario after the second night, deduce that they themselves have blue eyes and leave on the third night.
How do they conclude this? All three blue-eyed people hypothesize that if they themselves have brown eyes, then there are only two blue-eyed people on the island who, in turn, hypothesize that if they themselves have brown eyes, then there is only one blue-eyed person on the island. That hypothesized single blue-eyed person will deduce that he has blue eyes and leave on the first night as a result of the outsider's statement. But if no-one leaves on the first night, then that falsifies the hypothesized two blue-eyed people's hypothesis, so they would leave on the second night. But if no-one leaves on the second night, that falsifies the hypothesis of the three blue-eyed people, so they will all leave on the third night.
Conversely, the brown-eyed people will observe the three blue-eyed people leave on the third night and deduce that they themselves have brown eyes. The same style of reasoning applies to the 100 blue-eyed people scenario, with the blue-eyed people leaving on the 100th night and the remaining islanders deducing that they themselves have brown eyes.
So the outsider's statement did enable everyone to deduce their eye colors. But what new and useful information did it convey? In the single blue-eyed person scenario, it informed the blue-eyed person that someone had blue eyes. In the two blue-eyed people scenario, it informed the two blue-eyed people that the other blue-eyed person knew that someone had blue eyes. In the three blue-eyed people scenario, it informed the three blue-eyed people that the other blue-eyed people knew that the other blue-eyed people knew that someone had blue eyes. And so on.
In other words, the information that at least one person had blue eyes had become common knowledge. This meant that they all knew it, they all knew that they knew it, they all knew that they all knew that they knew it, and so on ad infinitum.
Another way to think about this puzzle is that the blue-eyed people know that they are either in a 99 or a 100 blue-eyed people scenario, but they don't know which one. Whereas the brown-eyed people know that they are either in a 100 or a 101 blue-eyed people scenario, but they also don't know which one. So the blue-eyed people will wait to see if the other blue-eyed people leave the island on the 99th night. If they do not leave, then the blue-eyed people deduce that they are in the 100 blue-eyed people scenario, and leave on the 100th night. The brown-eyed people observe the blue-eyed people leave the island on the 100th night, deduce that they are in the 100 blue-eyed people scenario, and thus know that they themselves have brown eyes. But remember that no-one will leave the island without the outsider's statement since her statement is necessary to falsify or confirm each persons' deeply-nested hypothetical about what the others know.
The key to solving this puzzle is to recognize that it has a recursive structure, observe the pattern that emerges with the simpler scenarios, and then apply that pattern to the more complex 100 blue-eyed people scenario. It's like the pattern that emerges when solving the factorial of four (or 4!). 4! = 4 * 3!, 3! = 3 * 2!, 2! = 2 * 1!, 1! = 1. Once the base case of 1! is solved, and the factorial pattern is understood, it's then easy to solve for higher-numbered factorials.
For some other expositions of the blue eyes puzzle, see xkcd and Terence Tao.
[Added Sep 24]
Bonus question: In a different version of the puzzle, the outsider comes back the day after making her public announcement, calls together all the people on the island, and makes a new public announcement:
"I'm terribly sorry, but I retract my statement from yesterday. I had a migraine that caused me to not see colors correctly so I don't actually know that I saw someone with blue eyes."
What effect (if any) will the outsider's new statement have?
The "am I in the 99 or 100 group scenario" that blue eyes wonder and "am I in the 100 or 101 group scenario" that brown eyes wonder is the way I tend to think of the situation. Although I feel it requires on an abstraction that may not be real.
ReplyDeleteSpecifically, when you say "informed the three blue-eyed people that the other blue-eyed people knew that the other blue-eyed people knew that someone had blue eyes" there's a recursion of common information. But how many times can this nest before its only an abstraction. Because in the 100 person scenario the iteration up from the one person scenario seems to imply that the driving force of the 99 day wait is the "I know that 98 people know, that 97 people know that 96 people know .... " etc. This functions in an abstract sense that where n = 1 is true and n -1 implies n, but in actuality the population is just counting off the days to see if 99 people leave or 100 people leave or 101 people leave.
One of the comments on the Terrance Tao blog points out that any growth of the blue eyed population above 3 would act as a trigger for the existing population to leave.
The recant is particularly interesting. The visitor's initial statement acts as a trigger (assuming the population grow to 100 somehow). Everyone can see blue eyed people all the time, but the visitor's statement synchronizes the potential to leave, so long as everyone understands it as a synchronizing trigger.
Thus when they recant, I think the reaction depends on whether people all understand that the trigger is gone. But because they know that there are blue eyed people, it would be impossible to escape that the trigger was real, even after the recant. And if no blue eyed people left on day 100, then some among the brown eyed population might think the trigger still counted and assume they were blue eyed and leave the next day.
"... but in actuality the population is just counting off the days to see if 99 people leave or 100 people leave or 101 people leave."
DeleteI think that's fine. The "counting off the days" method is logically equivalent to the "nested hypotheses" method, just as calculating a factorial in a non-recursive loop is logically equivalent to using recursion. But to preserve the logic, the counting-off can only begin when it is common knowledge that there is at least one blue-eyed person.
"One of the comments on the Terrance Tao blog points out that any growth of the blue eyed population above 3 would act as a trigger for the existing population to leave."
The commenter is incorrect. Without the common knowledge produced by the outsider's public statement, no-one can know how many blue-eyed people there are, and so no-one will never leave the island. Only if a (hypothesized) single blue-eyed person can know they have blue eyes, and leave the island, is it then possible for two (hypothesized) blue-eyed people to know they have blue eyes, and leave the island, and so on.
With the following day retraction, I think it helps to consider what the islanders have already learned after the first night when no-one left the island. After the first night it is common knowledge that there are at least two people with blue eyes (since the nested hypothetical scenario with one blue-eyed person was disproven by the observation that no-one left the island).