Here is a discussion of how one might approach the problem Gonna Make Your Brown Eyes Blue, with a detailed solution included. We note that the answer is actually under debate; even some professional mathematicians disagree with it!

Here’s the question:

Gonna Make Your Brown Eyes Blue 

1,000 mathematicians live on an island. 600 have brown eyes, and 400 have blue eyes. According to an ancient tradition which is honored by all, if a person ever discovers that they have blue eyes, they will promptly kill themself the following morning.

There are no reflective surfaces on the island, and it is considered to be in very poor taste to discuss the subject of eye color. Of course, everyone knows what everyone else’s eye color is.

One day, a soothsayer passes through the island, and in the presence of the assembled inhabitants solemnly announces: “At least one of you on this island has blue eyes.”

1. What happens?
2. What information was divulged by the soothsayer that wasn’t common knowledge before?
3. Extra credit: suppose each of the blue-eyed inhabitants had resolved not to leave the island if they ever discovered their eye color. What happens now?

 

We now talk about how to approach this problem. The solution below is by Craig Corsi, modified and expanded by Steven Miller.

So the first step before we tackle any of the questions is to try to understand completely what’s being asked.

First Thoughts: First, let’s take note that the inhabitants are mathematicians, and we assume that all mathematicians have not only perfect memory but a perfect logical capacity, always acting according to reason. If someone discovers they have blue eyes, then they won’t have a change of heart and go against the tradition (except in the scenario given by the bonus problem). So something very strange could happen, as long as all inhabitants are acting according to reason.

There are 1,000 total inhabitants, 600 of which have brown eyes, 400 blue. We don’t know yet what significance the numbers 1,000, 600, and 400 have. The fact that the numbers are even or multiples of 100 could mean something. Let’s put that detail aside for now, but note that it’s often worthwhile thinking about why certain numbers appear in a problem. Often it’s a good idea to try a similar problem with smaller numbers in an attempt to get a feel for the key issues

If someone discovers that they possess blue eyes, then they kill themself at the beginning of the next day. We note what might be an important distinction: the kill is not immediately after the discovery, but rather, it is at the beginning of the next day. In other words, the possible times for people to die can be treated as the natural numbers (the first day, the second day, the third day…) as opposed to the real numbers (4:35PM and 3.14159… seconds).

Then: “There are no reflective surfaces on the island, and it is considered to be in very poor taste to discuss the subject of eye color.” What this seems to be saying is that under ‘normal conditions,’ no one is going to discover their eye color. This is a reasonable thing to assume, and so let’s assume it and see what happens.

Next, everyone knows everyone else’s eye color. Okay.

Now a soothsayer appears and informs everyone simultaneously, “At least one of you on this island has blue eyes.” Everyone seems to know this already, because everyone can see everyone else. So how can there be any new information, and what can this information possibly DO?

 

Second Thoughts: So you probably realize by now that it may be best to tackle question 2) first: “What information was divulged by the soothsayer that wasn’t common knowledge before?” From there we can determine the more general 1): “What happened?”

Here are other preliminary thoughts:

Each blue-eyed mathematician sees the same number of blue and brown eyed people as all the other blue-eyed people (that is, 399 blue-eyed people and 600 brown-eyed people). Likewise, each brown-eyed mathematician sees the same distribution of eye colors as all other brown-eyed mathematicians. So if there’s no word-of-mouth communication allowed, then each blue-eyed mathematician has the same experience as the others and thus will go through the same thought process. Therefore, if one person with blue eyes discovers his eye color, then it seems reasonable that the other people with blue eyes will conclude the same thing about themselves. Then, if one blue-eyed person kills themself, then the others will too, and at the same time. 

But when? The morning after the soothsayer speaks? (We’ll refer to this as the “first morning” and other mornings accordingly.) Probably not, because the blue-eyed person the soothsayer talks about could be one of the 399/400 OTHER people, and what reason is there for someone to believe that they are the 400th/401st? 

The second morning doesn’t seem like a reasonable answer, nor do the the third or fourth or any morning in particular. Maybe the 400th morning, since there are 400 of them? A good reason for that is not apparent at this point in time.

 

Third Thought: Let’s go back to 1,000, 600, and 400. Are these numbers special, or does an analogous result hold for 500, 30, and 470 (or some other choice of numbers)? Should we examine a more general setting with n blue-eyed people, and m brown-eyed people?

Maybe. Sometimes, even though a general result is much stronger, it can actually be easier to prove.

Perhaps you’re thinking: “But the general result has infinitely many cases, and we can’t check all of them by brute force!” No, but we can check the first few cases and try to find a pattern. Sometimes the first few cases don’t suggest a pattern, or they misleadingly suggest a pattern that isn’t there. But sometimes they suggest not only the correct pattern but a means of proving that the pattern is true, and in general it doesn’t hurt to check the cases that are quick and easy.

Okay, but cases of what? Small total number of inhabitants? Small number with blue eyes? Small number with brown eyes? Let’s go with the second of these three options, since the blue-eyed people are the interesting ones — the ones whose fates seem to be at stake here.

(0) There can’t be zero people with blue eyes if the soothsayer is telling the truth.

(1) If only one person has blue eyes (say out of 2000), then that person will look around at the congregation of island inhabitants and see no blue eyes- only brown. The only reasonable conclusion, then, is that they themself must have blue eyes, since the soothsayer can’t be lying. Then that person will die on the first morning.

(2) Why is this important? Now we consider the case when two people have blue eyes. Let’s take the point of view of a blue-eyed person. “I see one person with blue eyes. If I have brown eyes, then that person is going to realize they have blue eyes and die tomorrow morning.” The next morning, no one dies. Then the same person thinks, “Okay, so then yesterday that person must have seen another pair of blue eyes. No one else on the island has blue eyes, so he must have seen MY blue eyes. I guess I have to die tomorrow.” BOTH blue-eyed people are going through this process at the same time, and they do not talk to anyone about it. Therefore, both blue-eyed people discover their eye color simultaneously and kill themselves on the second morning.

(3) In the case of three blue-eyed people, each blue-eyed person thinks: “I see two people with blue eyes. Suppose I have brown eyes. Then each of those two will go through the thought process in the paragraph above. But, what’s this? The second morning has passed, and no deaths. Then there must be a third set of blue eyes, and it must be me.” The other two blue-eyed people think in this way, and so all three die on the third morning.

(n) We see a pattern. Here’s a proof of the general result that n blue-eyed people will all simultaneously depart on the nth morning, for n > 0 (Furthermore, the brown-eyed people do not). We proceed by induction on n.

 

Note: this is a great opportunity to introduce students to proofs by induction, a powerful technique that allows us to handle infinitely many cases at once. We’ll stop the analysis of the riddle and talk a bit about proofs by induction,

So we want to prove that something is true with respect to some quantity n, where n could be any natural number. An example statement might be: Prove that, for n >= 3, the sum of the interior angles of an n-gon is (n – 2)*180 degrees. Recall that the natural numbers usually start with 1, so that we can speak of “the first case, the second case, the third case…” Sometimes we have to add a few extra cases or throw a few out which don’t make sense, but that’s okay. In the example above, the result doesn’t make sense for n = 1 or n = 2, so we concentrate on n = 3 or more.

Here’s what’s crucial. We want to say the following: “Well, it holds for the first case. And since it holds for the first case, it holds for the second. And since it holds for the second, it holds for the third. And so on and so forth off to infinity. Therefore, it holds for all cases.” But that’s not mathematically rigorous.

So instead, we show the following two things:

-“It” (the property we are trying to prove) holds for the first case.

-For any natural number k, if it holds for the (k – 1)-th case, then it also must hold for the k-th case.

These imply that the property holds for all cases that we are considering. The proof of this implication assumes what is known as the Well-Ordering Principle, which states that every non-empty subset of the natural numbers has a smallest element. More information on this can be found here:

http://en.wikipedia.org/wiki/Mathematical_induction

http://en.wikipedia.org/wiki/Well-ordering_principle

 

Here’s the statement again (our natural numbers begin with 1, as usual): Consider the island problem with n blue-eyed people and m brown-eyed people. Then, for any n and m, all n blue-eyed people leave the island on the nth morning, and none of the brown-eyed people leave the island.)

PROOF. By induction.

For n = 1 and for any m, the person with blue eyes will see everyone else at the gathering. Since each other person has brown eyes, and there exists a person with blue eyes, this person then concludes that they themself have blue eyes. By following the tradition, they die on the first morning. Furthermore, each brown-eyed person sees one person with blue eyes and reasons: “If I have brown eyes, then the blue-eyed person will realize they have blue eyes and die on the first morning. If I have blue eyes, then this will not happen. in other words, I have brown eyes if and only if the blue-eyed person dies tomorrow.” Since the blue-eyed person indeed dies the next morning, the brown-eyed people conclude that, indeed, their eyes are brown. In particular, they do not believe that their eyes are blue, and they do NOT die.

 

Now, assume that the result holds true for (k – 1) blue-eyed inhabitants and any number of brown-eyed inhabitants. Suppose now that there are k inhabitants with blue eyes, and any number of people with brown eyes. Each blue-eyed person will reason: “I see (k – 1) people with blue eyes. If I have brown eyes, then (by the induction assumption) the blue-eyed people will all kill themselves on the (k – 1)-st morning. So if they don’t kill themselves, then I must have blue eyes.” No one will have died by the (k – 1)-st morning, and so each blue-eyed person confirms their  eye color and dies on the k-th morning. Furthermore, each brown-eyed person will see k blue-eyed people kill themselves kth morning and conclude: “this could only happen if I myself did not have blue eyes. Therefore, I have brown eyes,” and none of the brown-eyed people die.

By the principle of mathematical induction, the result holds for all values of n blue-eyed people and m brown-eyed people.                                                                                                                         Q.E.D.

 

I leave the bonus question to you. I will say that much of the conceptual work has already been done; it just needs to be taken a step further. Once you have the solution, it’s a good exercise to try to write up a formal proof, in the style of what’s been written above.

 

Happy hunting!