display | more...
Answer to blue-eyed suicide - a math problem:
If there are n blue-eyed persons on the island, they will all commit suicide on the n-th night.

Proof:
The proof is by induction:
Clearly, if n=1, the one blue-eyed person, would commit suicide the night of the oracle's proclamation. This blue-eyed person knows that everybody else on the island has brown eyes; but since the oracle has said there must be at least one blue-eyed person, our blue-eyed person knows it must be him/her.

Now, let some n be given, and assume that the following statement is true: "If there are n blue-eyed persons on the island, they will all commit suicide on the n-th night (i.e. each of them can prove to his/herself on the n-th day that s/he has blue eyes)". I will show that this implies that the statement is also true for n+1.
Suppose there are n+1 blue-eyed persons on the island. On the n+1-th morning, each blue eyed person would look around and see that none of the n blue-eyed people that s/he can see had committed suicide. But by our inductive hypothesis, that means there must be at least one more, and they can see only n blue-eyed persons, each has proof that s/he is also blue-eyed. They all commit suicide that night.

This is a pretty tricky problem. To get a better grasp on it, consider the case where there are only three islanders, two of whom have blue eyes. On the morning after the oracle's fateful pronouncement, each blue-eyed person sees that the other blue-eyed person did not commit suicide. This tells blue-eyes #1, for example, that blue-eyes #2 must know that someone else has blue eyes. This can only be #1 himself, and thus he has the fatal proof.

Food for thought:
What is the importance of the oracle in this story? (I'm not telling here... /msg me and I might ;)

thax's answer contains a proof by mathematical induction. It's a great way to prove things you already suspect, but it doesn't help much in finding an answer without knowing it in advance. I will now give a painfully detailed example of how one might do this.

You can begin to develop the suspicion by stating everything you know about the case, even trivial ("obvious", not unimportant) things:

  • Here in the magical land of predicate logic, proof is truth, truth proof. Only blue-eyed islanders (if anyone) can ever prove themselves to be blue-eyed, and so only blue-eyed islanders (if anyone) will commit suicide.
  • This is a bona fide math problem, not some dumbass riddle. You've been given all the information you need to solve it. There are no births, migrations, or deaths other than suicide, no suicide at any time other than midnight nor for any reason other than deducing at or after the previous midnight that one has blue eyes. No blue-eyed person ever fails to figure it out if they have the information to do so. The only information available besides what the oracle just said is how many other people have blue eyes (and how many have brown eyes, which is equivalent by way of subtraction from 1000).
  • Symmetry is key. There are two groups of islanders, and everyone in each group is exactly the same (for purposes of the problem) as everyone else. This has the rather significant implication that, if any one (blue-eyed) islander commits suicide on a given night, they all do.

We now know that the blue-eyed freaks will either live forever in blissful ignorance or drink the grape Flavor-Aid together on some night determined by how many of them there are and nothing else. Now it's time to explore particular cases from the perspective of a freak (since at least one must exist):

  1. Nobody else is a freak. It's obvious you're the one. You kill yourself on the first night.
  2. Only one other guy is a freak. Either you aren't, in which case he kills himself on the first night as above, or you are, in which case you both are following this line of reasoning, each learn that you are a freak when the other doesn't kill himself on the first night, and both kill yourselves on the second night.

Right away you get recursion: the decision of each freak in a set of two is derived in an obvious way from that of a freak acting alone. Having discovered the base case and how to extend it by recursion, you are now ready to dive into the inductive proof, as above. (Sometimes it takes a while to get to the recursive part. You have to be careful to ensure that it works for all cases other than the base case, or you'll end up proving that all horses are the same color.)

Log in or register to write something here or to contact authors.