CS W1007x Introduction to Computer Science
Eric Siegel, Columbia University

The Oracle Problem


Warning: This problem will drive you crazy and make your brain melt.

The situation. There is an island with 100 blue-eyed folks. Nobody knows their own eye color, there are no reflecting surfaces on the island. Everyone knows the following rules and obeys them: You may not speak about eye color at all, and if you somehow deduce your own eye color, and find out it is blue, you must kill yourself that night at midnight. That would be bad, so let's not discuss it.

Nobody is color-blind. Eric Siegel is color-blind, but that has nothing to do with it. They have lived together for years, and thus are familiar with everyone else's eye color. Everyone is an amazingly perfect logical deduction machine. Nobody will communicate about eye color at all in any way. Everyone sees everyone else at least once a day, because they all work in the same factory making widgets. They hope that one day they will have a corner on the international widget market. There are two obstacles to this, though: They are completely isolated on this deserted island, and they may all kill themselves sometime soon. Note that everyone is a direct descendant of Giligan.

But one day an Oracle floats down from, like, Cleveland, or somewhere. Nobody can believe it because before this supernatural activities were not compatible with their belief system. This is a very primitive prime-time sitcom island that has not progressed very far culturally. For example, most inhabitants believe Bob Barker still has brown hair.

Anyway, the Oracle announces the fact that, "There are blue-eyed people on this island!" (This should be interpreted as, "there is at least one person with blue eyes.") Everyone is totally offended that he broke the rule so they zap him with a photon ray gun set to kill. He is now gone. His eye color does not matter for this problem.

The question: What happens next?

Hints: Note that he didn't say anything that everyone didn't already know. Also note that there is nothing differentiating anyone from anyone else. Therefore, anything that you deduce about any one individual would also apply to everyone else.

To solve this, first pose the same problem but with an island that has 2 blue-eyed folks and 98 green-eyed folks and the same rules.

Solution: They all kill themselves on the 100th night.

Related problems: Andrew Kosoresow told me this problem is also known in different forms: the tenured professors problem, the muddy childrens problem, the cheating husbands problem.

Proof: If the original problem had been posed with 1 blue eyed person (and 99 of another color), it is obvious in this case that indeed this sad, blue-eyed, soon-to-be-dead person would in fact learn something from what the Oracle said. (The other 99 would not, however, since they already knew there was at least that one blue-eyed person.) The blue-eyed person then spends the rest of the day seeming slightly pre-occupied. When people ask, "what's wrong, Allen?" he just shrugs it off, "oh, nothing, I just stubbed my toe." But that night he'll slip himself a mickey. No, not mickey mouse, a poison.

Ok, what if the original problem had been posed with 2 blue eyed folks, and 98 of another color? Well each of these two would not know their own eye color. Therefore, each would think, "either that person is the only blue-eyed person, or I also have blue eyes. If I do not have blue eyes, they will kill themself tonight" (by the reasoning above). Therefore, when they see one another alive the next day, it hit's them. "Oh my god," they'll think, "I must have blue eyes, too. Therefore, I have to kill myself tonight. Therefore, I'll never get the opportunity to be on Letterman." Note that this thought process is unique to these two -- the other 98 see 2 instead of 1 blue-eyed person.

Ok, if there were 3 with blue eyes, each of those three would think, "If I have non-blue eyes, then there are only two blue-eyed people, in which case they'll kill themselves tomorrow night" (by the reasoning above about 2 blue-eyed people). Since they don't, they realize it is death time on day 3.

If there are n with blue eyes, each of those n would think, "If I have non-blue eyes, which gosh I really hope is true, then there are only (n-1) blue-eyed people, in which case they'll kill themselves on the (n-1)-th night." But they don't, so on the n-th night, all n blue-eyed people lock themselves in a room with a television playing re-runs of "The Partridge Family". Death is almost instantaneous.

Understanding the solution. This proof looks at it from the bottom up. If you want to look from the top down, given that all 100 people have blue eyes, it ends up being a bunch of nested hypotheses. Basically each person thinks, "if I have non-blue eyes then each blue-eyed person is thinking, 'if I have non-blue eyes then each blue-eyed person is thinking, if I have non-blue eyes then each blue-eyed person is thinking, ......'..."

This doesn't go on forever, however. Rather, it gets down to one hypothetical blue-eyed person (the "base case"), who, it is easy to prove, would kill her or his hypothetical self. Try thinking it through for a population of 4 blue-eyed folks.

Relevance to computer science: The proof above is a (somewhat informal) proof by induction. More such proofs are covered in discrete structures math courses. This type of proof is useful for all sorts of computer science things, like showing that certain digital circuitry works, and proving that recursive functions work.

It is also relevant, abstractly, to modular decomposition. It is very hard to think about and understand this entire "system" of blue-eyed people all-at-once. Similarly, it is just as hard to think about how large computer programs work all at once. In both cases, you must break down the problem and only focus on one sub-problem at once.

Finally, it is abstractly relevant to computer networking. Where do you draw the line when posing a question such as, "computer A verified that computer B verified that computer A verified that computer B verified... that computer B got A's message." The answer is, unless you go on forever (which would take a really long time), you cannot create a sure-fire protocol that is 100% dependable between two computers (or people, for that matter). (This is often framed as the "two army problem".) Likewise, we have a similar nesting of conditions/hypotheses shown above.