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)