The Blue Eyes Problem and Solution

The problem is this (Source: Terence Tao blog):

There is an island upon which a tribe resides. The tribe consists of 1000 people, with various eye colours. Yet, their religion forbids them to know their own eye color, or even to discuss the topic; thus, each resident can (and does) see the eye colors of all other residents, but has no way of discovering his or her own (there are no reflective surfaces). If a tribesperson does discover [that] his or her own eye color [is blue], then their religion compels them to commit ritual suicide at noon the following day in the village square for all to witness. All the tribespeople are highly logical and devout, and they all know that each other is also highly logical and devout (and they all know that they all know that each other is highly logical and devout, and so forth).

[Added, Feb 15: for the purposes of this logic puzzle, “highly logical” means that any conclusion that can logically deduced from the information and observations available to an islander, will automatically be known to that islander.]

Of the 1000 islanders, it turns out that 100 of them have blue eyes and 900 of them have brown eyes, although the islanders are not initially aware of these statistics (each of them can of course only see 999 of the 1000 tribespeople). [irrelevant]

One day, a blue-eyed foreigner visits to the island and wins the complete trust of the tribe.

One evening, he addresses the entire tribe to thank them for their hospitality.

However, not knowing the customs, the foreigner makes the mistake of mentioning eye color in his address, remarking “how unusual it is to see another blue-eyed person like myself in this region of the world”.

What effect, if anything, does this faux pas have on the tribe?

[bolded] is my edit, edited so my explanation jives with the brain teaser.

The answer is that all the islanders with blue eyes die. Here’s why.

Let n be the number of people with blue eyes. Consider the case n=1. The guy with blue eyes sees nobody else with blue eyes, and so kills himself on the first day (“Day 1”) after the foreigner makes the announcement.

Now consider n=2. Each person with blue eyes sees another person with blue eyes. Let’s use the perspective of Person 2. Person 2 sees one person with blue eyes, Person 1, so he expects Person 1 to kill himself on Day 1. But Person 1 doesn’t, because by symmetry, Person 1 sees the same thing as Person 2. Thus by the fact that Person 1 is alive on Day 1, Person 2 realizes Person 1 sees a person with blue eyes. As there are no other people with blue eyes, Person 2 realizes he must be it. Again by symmetry, Person 1 makes this realization as well. Both kill themselves on Day 2.

n=3 becomes a little complicated. Person 3, let’s say, now sees Person 1 and 2 with blue eyes. Nothing happens on Day 1, this is not unusual. But by Day 2, the preceding paragraph would imply Persons 1 and 2 would have killed themselves — so they have to had seen a third person. So Person 3 reasons that, having seen no other third person with blue eyes, he is it. By symmetry, Persons 1 and 2 make the same realization. On Day 3, they all kill themselves.

Now this can be iterated indefinitely. For example, in the n=4 situation, on Day 3 Person 4 would expect Persons 1, 2, and 3 to have killed themselves by the above paragraph. But they are still alive, so they each saw another person with blue eyes. Having seen no other set of blue eyes, Person 4 realizes he is it, and by symmetry, Persons 1, 2, and 3 simultaneously make this realization. They all die on Day 4. In general, on Day (n-1), each person with blue eyes expects all the other people with blue eyes to kill themselves, since each person with blue eyes sees (n-1) sets of blue eyes. When nobody dies, every person with blue eyes deduces all the other blue-eyed people see him. As all make this realization on Day (n-1), all die on Day n.

Well, you ask, how about the brown-eyed people? They are irrelevant to this problem. They see n sets of blue eyes, instead of n-1. As such, the decision making of the brown-eyed people is delayed to Day n, when all the blue-eyed people are dead, vindicating the brown-eyed people. The number of brown-eyed people does not change the number of blue-eyed people that are seen by each blue-eyed person, which is what matters.

Another objection that comes up is that the foreigner doesn’t give any new information, because everyone can see who has and has not blue eyes. The key is that there is an exception to this, for the base case n=1, where the foreigner would inform the blue-eyed person that he is it. Without the information, nobody would kill themselves even if there was one blue-eyer on the island. But now, since n=1 happens, n=2 must happen, and so on… In other words, the foreigner provides a logical pathway for someone to find out he has blue eyes. Without the foreigner’s statement, nobody could ever find out that he has blue eyes, thus nobody could ever kill himself, and thus nobody expects anybody to kill himself. If one person could kill himself from blue eyes, then all people with blue eyes are doomed, because everyone with blue eyes would wait until all the other people with blue eyes are dead — until he realizes there is one more set of blue eyes, those belonging to himself.

Advertisements

2 Comments

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s