Eye color probability puzzle

Question

I went to a talk about probability paradoxes, and the speaker mentioned the following scenario (at least, this is how I recall it):

One hundred people live on an island. Each person has green or blue eyes. Each person knows everyone's eye color except his own, and they don't communicate with each other. A traveler comes to the island and tells the inhabitants something that everyone already knows. For example, if all except one of them had blue eyes, he could tell them "at least one of you has blue eyes."

The counterintuitive thing is supposed to be that the traveler's statement will actually give new information to someone. I am not seeing how this is true. Maybe I misinterpreted the setup?

Answer 1

The traveler's statement gets everyone on "the same page" so that each islander can correctly deduce what the other islanders know. Imagine a case with one person with blue eyes and one with green. The person with blue eyes can't see anyone with blue eyes, so the traveler's statement that "there is someone here with blue eyes" is in fact new information to him.

Now imagine two people with blue eyes and one with green. Both blue eyed people can see someone else with blue eyes, so the traveler's statement isn't really new information - of course there's someone here with blue eyes. However, each blue eyed person doesn't know that the other blue eyed person can also see someone with blue eyes. After no one leaves on the first day, each blue eyed person can correctly deduce that the other blue eyed person must have seen someone with blue eyes, and it must be themselves.

The traveler's statement allows the islanders to figure out what each other islander knows. The statement itself doesn't give information directly, but how the other islanders react provides clues about who has bue eyes. To sum it up, even if I know that someone here has blue eyes, I don't know that my neighbor knows that until the traveler tells me.

Answer 2

Imagine a simplified setting where there are only two island inhabitants: one with blue eyes and one with green eyes. They can each see each other's eyes, but they cannot see their own. Hence they know the other person's eye color, but not their own. When the traveler arrives and states that at least one person has blue eyes, the person with blue eyes immediately knows that they have blue eyes, since they can see that the other person does not. Hence they have learned something new.

Of course, this doesn't exactly scale up---if there are more people on the island and at least two of them have blue eyes, there isn't really any new information provided by the traveler. However, in your question with 100 inhabitants, there is an important part of the puzzle that you left out. The problem is usually stated as follows:

There is an island on which 100 people are stranded, 99 with blue eyes and 1 with green eyes. There is a boat moored at the island, but the boatman won't let the islanders leave until they can tell him how many people on the island have blue eyes. Each morning, the islanders send a representative to talk to the boatman, who asks if they know how many people have blue eyes. One morning, the boatman, getting tired of this game, tells the representative that at least one of the islanders has blue eyes. Can the stranded islanders every leave?

The answer is yes, they can, because the boatman has given the islanders something that they didn't have before: a point of reference in time. The new piece of information is common clock that all of the islanders can refer to. To see why this helps, again consider a smaller problem. Suppose that there are only three people on the island, two with blue eyes.

Suppose that Alice and Bob have blue eyes, and that Carol has green eyes. On the first day after the boatman tells them that at least one person has blue eyes, Alice sees that Bob has blue eyes and that Carol has green eyes. So, as far as Alice is concerned, Bob could be the only person on the island with blue eyes, or both Alice and Bob could have blue eyes. Bob reasons similarly, and Carol reasons that there are either two people or three people on the island with blue eyes. On the first morning, they can't leave, because they don't have enough information.

However, when they don't leave on the first morning, they have gained more new information: no one knows the number of people with blue eyes, which means that everyone can see at least one person with blue eyes and, since they don't know their own eye color, there could be at least two people on the island with blue eyes. On the other hand, Alice and Bob each know that there can be at most two people on the island with blue eyes, since they can see that Carol does not have blue eyes. This tells Alice and Bob that there are exactly two people with blue eyes, so they can go tell that to the boatman, and everyone leaves.

The process is similar with more people, it just takes longer.