## Monday, August 17, 2009

### Eye Color Riddle

I got this problem during our most recent hiking trip. It served as a fun distraction and a way to kill time during our downhill hike. I will post the solution in about a week's time. Please feel free to post yours in the comment. The riddle credit goes to Vallent Lee.

On an isolated island there are 50 people with blue eyes, 50 people with brown eyes, and an oracle with green eyes. Every day at noon, a ship comes to the island. Anyone who can correctly mention his or her eye color can board the ship and leave.

One day, the oracle says "there is at least one person with blue eyes."

Who leaves the island and when?

1. Observe that people without eyes receive no extra information since they already knew that there was at least one person with blue eyes, being able to see everyone else. Hence, we can conclude that these people will never leave the island.

One might argue that on the island in question, a blue eyed person can see the other 49 people with blue eyes and hence also do not receive new information, but this is not true in the general case, as will be argued below.

Consider the base case where there is only one person with blue eyes on the island. On the first day that person would immediately see that everyone else does not have blue eyes so he himself must have blue eyes. Thus, he leaves.

Now consider the case where there are two blue eyed people. Each blue eyed person sees that there is exactly one other blue eyed person. Each blue eyed person can assume for the sake of contradiction that their eye color is not blue. Thus, they would expect that on the first day, the other person would leave. Since no one leaves on the first day (no one has enough information), the assumption that their eye color is not blue is false. Hence, their eye color is blue and both blue eyed people leave.

We can generalize this to an island with n blue eyed people (and m non-blue eyed) using induction. Our induction hypothesis is that on an island with k blue eyed people all the blue eyed people leave on the kth day. This hypothesis holds for k=1 as shown above.

For k+1 blue eyed people - Each blue eyed person assumes that their eye color is not blue. On the kth day they expect all k of the other blue eyed people to leave by the induction hypothesis. This does not happen on the kth day, so the assumption must be false. Hence the induction hypothesis holds for k+1.

We have now shown that the hypothesis holds for all positive integers k. For the puzzle above, k=50.

2. everybody except the oracle leaves by the second day. they'll all guess blue the first day and then brown the second. oracle has no idea green eyes exist. some oracle.

3. I'm supposed to post a correct solution about now, but savagenumber's solution above is the correct one. So there you go...