Problem:
There is an island inhabited by monks who are very intelligent but have
some very rigid rules that they live by. For one, they believe that blue
eyes are evil and if a monk finds out she has blue eyes she must kill
herself *that very day*. Another rule is that, despite everyone seeing
each other every day, they cannot communicate in any way whatsoever.
That, combined with the fact that there are no reflective surfaces on the
island, means that the blue-eyed monks never find out their eye color and
so all is good for years and years.
But one day a visitor comes to the island and before they leave, remarks
for all to hear that they've never seen such beautiful blue eyes as on
this island.
Assumptions:
- every monk sees every other monk all the time.
- it is common knowledge on the island that all monks are rational
and obey all monk protocols perfectly.
- monks reason instantly and if one concludes that she has blue eyes
she will commit suicide by sunset of that day.
- the visitor's announcement is made publicly.
- the visitor adds nothing but that observation (that there exist
blue eyes on the island).
What happens?
Conjecture:
If there are n blue-eyed monks on the island, they will all
commit suicide on the nth day.
Proof (by induction on n): (skip to the "For example" for a less
mathematical solution)
Base Case: If there is only 1 blue-eyed monk, the visitor's
announcement will prompt that monk's suicide the same day, day 1.
General Case: Assume that with n blue-eyed monks on the island, they
will each commit suicide on day n. Prove that with n+1 monks on the
island, they will each die on day n+1. This is true because if there are
n+1 blue-eyed monks then each of them will *observe* n blue-eyed monks.
Thus, by the induction hypothesis, they will expect (hope) that the n
monks they observe will all commit suicide on day n. When this doesn't
happen, the only explanation can be that there are *not* in fact n
blue-eyed monks. There must be an additional, unseen, pair of blue eyes
-- their own. All following identical reasoning, they each realize their
fateful eye color at the end of the nth day, and on day n+1 they each
commit suicide. QED
For example: Suppose there are 2 blue-eyed monks on the island and
you're one of them. Before the visitor arrives you always assume that the
blue-eyed monk you observe is the only monk with blue eyes -- ie, you're
safe. (That monk is of course thinking the same thing about you.) When
the visitor announces that there are blue eyes on the island you expect
the *one* (so you think) blue-eyed monk to commit suicide. When they
don't, you realize you're in trouble. They must have been watching
someone else and waiting for that person to commit suicide. The only
person that they could have been watching is you -- you can see that
everyone else on the island has brown eyes so that rules them out. So
because the other blue-eyed monk didn't kill herself on day 1, you deduce
on day 2 that your eyes are blue and you kill yourself. The other monk
went through identical reasoning watching you and so will also commit
suicide on day 2.
Supposing there are 3 blue-eyed monks, each is watching the other 2 and
expecting, by the reasoning above, that they will both die on day 2. When
they don't, she concludes that they must not be watching just each
other. Since it's symmetric, the other 2 monks are each watching you and
the other one and thinking the same thing. Hence, you all 3 know to kill
yourselves by the 3rd day. etc...
Follow-up question: It's clear that the visitor was necessary in the
proof in order to establish the base case. However, the only information
that the visitor provides (there exist blue eyes on this island) is
something that (assuming more than 1 blue-eyed monk) every single monk
already knew. The question: What was different after the visitor's
announcement? Ie, as a monk on the island, what do you know after the
visitor's announcement that you didn't know before?
Daniel Reeves -- Modified 2008.08.27 23:52:30 Wed (EDT)