Solution to Riddle of the Week

Solution to Riddle of the Week: The Blue-Eyed Islanders

Difficulty level: Very Hard

Michael Stillwell
 
By Jay Bennett

This riddle is a journey into mathematical logic and theory. Like the famous Monty Hall problem or Riddle of the Week #12: Licking Frogs, simply knowing the answer often isn't satisfactory. The reason why the answer is true is just as important, and it takes some good long pondering to grasp the why. So don't throw in the towel early on this one, and check the original problem here.

SOLUTION

It may be hard to conceptualize at first, but the pattern from the hint does in fact continue. All 100 blue-eyed people leave on the 100th night.

Let's take a closer look at this, picking up where the hint left off. You know that if there were only one person with blue eyes, they would realize it immediately after hearing the guru's statement because they see no one else with blue eyes. Therefore, that person would leave on the first night.

You also know that if there were two people with blue eyes, then they would both leave on the second night, because they would each look at the other blue-eyed person on the second morning and realize that the only reason the other blue-eyed person wouldn't leave on the first night is because they see another person with blue eyes. Seeing no one else with blue eyes, each of these two people realize it must be them.


Michael Stillwell

Now consider the case of three blue-eyed islanders. It has been established that if only two people had blue eyes they would leave on the second night. You, the third blue-eyed person in our example, know this, as do the other two blue-eyed people. So when you wake up on the third morning, and the two other blue-eyed people have not left, you know that they must see another person with blue eyes, and you can see that no one else on the island has blue eyes, so you know it must be you. All three of you realize this simultaneously, and all three leave on the third night.


Michael Stillwell

This is true for any number. Four people with blue eyes would leave on the fourth night, five on the fifth, and 100 on the 100th, all at once.

There are still some lingering questions about this problem, however. Specifically, what new information does the guru impart to the islanders when she says, "I see a person with blue eyes"? The islanders all already know that the guru must see a person with blue eyes—there are 100 of them milling about.

The answer is common knowledge. Now, we're not talking about the colloquial use of the phrase defined as something that many people know, such as "it's common knowledge that you should stay away from a mother bear." In game theory, common knowledge has a specific definition. There is common knowledge of a piece of information "p" in a group of agents "G" when all the agents in G know p, they all know that they know p, they all know that they all know that they know p, and so on ad infinitum.

In other words, there is a mathematical difference between all the members of a group knowing something, and all the members of the group knowing that everyone else also knows it, and then as a final tier, all the members of the group know that everyone else knows that everyone knows it.

Let's look at a quick example. Bob, Sally and Jim are a group of three people. I write down something on three pieces of paper and hand one to each of them, but they don't know what I've written on the other two notes. Let's say I write down, "there is a huge spider lurking above you," on all three notes. Then Bob, Sally and Jim all know there is a huge spider lurking above them, but that is not common knowledge. If I wrote on Bob's note, "there is a huge spider lurking above you, and Sally and Jim know it," and did the same thing with the other two notes, then Bob, Sally and Jim all know that there is a huge spider lurking above them, and what's more, they all know that the other two people know that there is a huge spider lurking above them. But that still is not common knowledge.

Only when I say out loud to the whole group, "there is a huge spider lurking above you," do Bob, Sally and Jim all know that there is a huge spider lurking above them, that the other two people know there is a huge spider lurking above them, and they all know that the other two know that everyone knows there is a huge spider lurking above them. That is the state of common knowledge, as first introduced by American philosopher David Lewis in 1969.

Each blue-eyed islander knows from looking around the island that there are 99 other people with blue eyes and 100 people with brown eyes. But because they cannot depart the island without being certain, they cannot begin the process of leaving until the guru speaks, and common knowledge is attained. Without knowing that everyone knows that everyone knows that there is at least one person with blue eyes, they cannot leave.

Go back now and think about if there were only two blue-eyed people on the island. If the guru never spoke, then they would not be able to leave on the second night, because they would not know that the other blue-eyed person should leave on the first night. Not until the guru speaks.

Unfortunately for the brown-eyed islanders, without that key piece of information—that everyone knows that everyone knows that everyone knows that there is someone with brown eyes—the chain of deduction cannot begin, and no one with brown eyes can leave.

I hope this information comes in handy if you are ever stranded on an island and have forgotten the color of your eyes—and I hope you come back next week for another riddle!