Common Knowledge

July 14, 2009
• General
• Puzzles

This one makes my head hurt.

Far away, there is a very odd island. There are many people on this island, and each person has either blue or green eyes. It's a very backward culture and they are very strict about their culture. The islanders have the following rule: If you logically know for sure that you have blue eyes, you must leave the island the next day at exactly noon. However, the island has no mirrors and people aren't allowed to ever talk about eye color. So, the people with blue eyes live on the island in ignorance of the color of their eyes.

One day a foreign sailor comes to the island. He is of course ignorant of their culture and makes a faux pas. He gathers all the islanders together in their central square and says to them: There is at least one person with blue eyes on this island.

What are the consequences of his saying this? One would think that there would be no consequences. Even though no one knows their own eye color, they can see the eye colors of everyone else on the island, so if there are several people with blue eyes, everybody knows that there are people with blue eyes. So, the sailor isn't telling the people anything that they don't know.

Or is he?

Let's think of the case where there is actually only one person with blue eyes on the island and the rest have green. The sailor makes his statement. The person with the blue eyes looks around and sees that everybody else has green eyes. Since there is at least one person with blue eyes, and he sees everybody else with green eyes, he must logically conclude that he has blue eyes. This man leaves the island the next day at noon.

What if there are two people with blue eyes. Let's call them person A and person B, and all the other people have green eyes. Well, person A sees person B has blue eyes, so he already knew that there is at least one person with blue eyes on the island. But something strange happens. The next day at noon, person B DOESN'T leave the island. Here's the key: If person B were the only person with blue eyes, he would have left the island at noon. Hence, person A must logically conclude that there are at least two people with blue eyes on the island. And since he sees only one person with blue eyes, he must conclude that he indeed has blue eyes. On the second day, person A leaves the island at noon. Similarly, person B comes to the same conclusion and also leaves the island along with person A.

What if there are three people with blue eyes? Person A, B, and C all have blue eyes. Person A knows that there are at least two people with blue eyes. But if he has green eyes (which he could in his mind), then person B would potentially only see one other person with blue eyes (person C). So, in the mind of person A, person B can see as few as 1 person with blue eyes and as many as 2. No one leaves after days 1 or 2. If there were exactly 2 people with blue eyes, than they would both leave after day 2. Thus, person A must conclude that there are 3 people with blue eyes, that he is one of them, and he, along with person B and C, leave the island after day 3.

etc

If there are K people with blue eyes, then they will all simultaneously leave the island after day K. And yet, the sailor has seemingly given the islanders no new information. The trick is that he presented them with common knowledge. He is an outsider to the game and has given everybody a logical statement that, in his giving it, everybody becomes aware of. And, more importantly, everybody also becomes aware that everybody is aware of it. They key is that everybody knows that he told the fact to everybody. The concept of knowing something, and knowing that everybody knows something, and knowing that everybody knows that everybody knows something... to infinity is logically called common knowledge.

This whole thing makes pretty much no sense to me and gives me a headache whenever I think about it too hard.