A group of people with assorted eye colors live on an island. They are all perfect logicians -- if a conclusion can be logically deduced, they will do it instantly. No one knows the color of their eyes. Every night at midnight, a ferry stops at the island. Any islanders who have figured out the color of their own eyes then leave the island, and the rest stay. Everyone can see everyone else at all times and keeps a count of the number of people they see with each eye color (excluding themselves), but they cannot otherwise communicate. Everyone on the island knows all the rules in this paragraph.The classical answer is that all blue-eyed islanders leave on the 100th night. The proof proceeds inductively - here's a nice explanation by a commenter on Terry Tao's blog. Note that this explanation uses slightly different formulation of the puzzle in which islanders must commit suicide (!!) if they learn their eye color (rather than simply leave the island).
On this island there are 100 blue-eyed people, 100 brown-eyed people, and the Guru (she happens to have green eyes). So any given blue-eyed person can see 100 people with brown eyes and 99 people with blue eyes (and one with green), but that does not tell him his own eye color; as far as he knows the totals could be 101 brown and 99 blue. Or 100 brown, 99 blue, and he could have red eyes.
The Guru is allowed to speak once (let's say at noon), on one day in all their endless years on the island. Standing before the islanders, she says the following:
"I can see someone who has blue eyes."
Who leaves the island, and on what night?
The induction certainly "works" in the sense that if start with your base case (k=1) and reason inductively, you are led to the theorem that after k days, all k blue-eyed people leave the island. But note what you must do to start off this inductive process - you must consider what would happen if k were 1. But in reality, no matter your eye color, you are certain it is impossible for k to be 1. I claim that considering the k=1 case is an arbitrary thing to do. Maybe it is natural that you happen to consider the k=1 case in light of the guru's announcement, but you are not logically compelled to do so. It is only if we assume the announcement will cause everyone to consider k=1, and further, that everyone knows the announcement will have this effect, that the proof goes through. As given, the problem is unclear.
Let’s use the letter k to represent the number of blue-eyed islanders, of which you will be one of. In the argument “I” is used so that you may read this aloud to yourself as if it were your own dilema.
If k is 1, then I cannot see any blue-eyed people on the island. This was fine until the visitor told us that they exist. But now, knowing that they do exist and not being able to see any, I can only conclude that it must be me! Thus, I must die one day from now.
If k is 2, then I can see only one other blue-eyed person, Joe. I know that Joe is as logical as I am so by the reasoning when k is 1, he’s going to have to kill himself. I check on him tomorrow and see that he hasn’t, but how can that be? The only logical conclusion is that the above reasoning did not apply for Joe because when he looked around he must have seen someone else with blue eyes. But I don’t see such a person so it means that it must be me! Thus the following day (two days after the information)I must die. But since Joe is as logical as I am and has been faced with the same situation, he must also have discovered, exactly as I did, that he has blue eyes. Thus he will kill himself at the same time as I do.
If k is 3, then I can see see two blue-eyed people, Joe and Ted. Now, here is where you see the argument continue to depend on the earlier cases (this is what is meant by induction). If Joe and Mike are truly the only two people on the island, then based on the exact same reasoning when k is 2, they will both be dead after two days exactly. However, after two days I see that both are still living. Again, the only logical conlusion is that when Joe and Ted looked around they must have seen someone other than each other with blue eyes. Since I can’t see such a person it means that it must be me! Thus I must kill myself the next day (now three days after the information). But, since Joe and Ted are equally logical, also have blue eyes, and have been part of the same situation, they must have learned exactly as I did that they too have blue eyes. They will join me at the suicide ritual on the same day.
At this point you can see the repetitive nature of the argument. For each higher value of k the argument is quickly formed in terms of our previous argument for k-1. The induction proof is merely a concise formation of this which (correctly) reasons in terms of a general value of k. The visitor’s information is essential because it sets up the “base case” where k is 1.
Note that we could do the exact same proof to argue that all j brown-eyed islanders would leave after j days, provided we assume that everyone will consider the j=1 case, and that everyone knows everyone else will consider this case. The only effect of the announcement (since it reveals no new information) is simply to act as a coordination device to determine which chain of reasoning is to be considered. In the absense of some way of coordinating which chain of reasoning to use, no one can be convinced that others will follow through with the reasoning, and the induction cannot proceed.