This was brought to my attention by G, and can be found at XKCD's site. My intention is to attempt at giving a clearer setup and clearer explanation of how to derive the answer.
This game can be solved using a bit logic, math, and a thought experiment. I'm sure there are a variety of ways to reach the solution, but I feel that I've stumbled across a relatively easy solution, though it may be less elegant than the others.
The Setup:
200 people--who are perfectly logical beings and completely aware of everyone else at all times--are trapped on an island. These people can see everyone else's eyes but NEVER their own (no reflection, etc.) and they have no means of communication whatsoever (no getting other people to tell you the color of your own eyes). Because they can never know the color of their own eyes, no one person knows the complete distribution of eye colors. They can only deduce the color of their own eyes from only what is given in the rest of this setup.
Every night at midnight, a ferry comes to pick up those who know, with absolute certainty, the color of their own eyes, and bring them back to the mainland.
One morning, a guru (who happens to have green eyes) descends on this colony of logical and aware beings and makes the statement (a true one): "I see a person with blue eyes." She then disappears to never return again.
The Problem:
If there are 100 people with brown eyes and 100 people with blue eyes, how many days does it take before people can start leaving? Who can leave and how many? The answer must include 1) the color of the eyes of the people leaving, 2) number of people leaving, and 3) the number of days it takes them to leave.
Before you go off trying to solve this, there are a few things to remember.
- There IS an answer to this puzzle that fits the criteria above and does not transcend the scope of the given setup. Id est, someone leaves on a certain day.
- No person initially knows the precise distribution of eye colors; that is, a person might see 100 brown eyed people and 99 blue eyed people, but does not know if he himself has brown eyes, blue eyes, or purple eyes (could be 101 brown eyes and 99 blue, or 100 brown and 99 blue and 1 purple, etc.)
- Remember that in order to leave, a person must know with absolute certainty!
- These people are capable of perfect logic, and know all and only what is given in the setup above.
More than arriving at the correct answer, it's more important (I think) on how you arrived at the answer. Please leave your thoughts (candidates, algorithms, and especially QUESTIONS REGARDING THE SETUP) in the comments section. I'll return periodically to leave hints and, eventually, the answer.
Luke used the bottom-up approach to this problem. By beginning at the simplest possible scenario, you'll find an emerging pattern. I'll begin by entertaining the thought process that a blue eyed would need to go through to achieve absolute certainty (after all, that's all that matters--you'll see later).
br = brown, bl = blue
199br, 1bl on island
The blue eyed person will realized that of the 200 people on the island, he is the only one who could have blue eyes. He leaves.
198br, 2bl on island
We'll assign letters to the two blue eyed people: A and B. A will see that B has blue eyes, and deduce that B will do the following: if B does not sees another blue eyed person, B will leave on day 1, but if B sees another blue eyed person--which must be A--B will wait to see if A leaves on day 1. Since A and B both see each other, they will both wait until day 2, realize that there must have been another blue eyed person, deduce that it is themselves, and leave that night.
197br, 3bl on island
A, B, and C have blue eyes. A will see that there are two blue eyed people and they will, at the very least, adopt the strategy above. Furthermore, if A happens to find that B and C do NOT leave on day 2, A can deduce that he has blue eyes.
There's really no point in going any further as you should see the pattern by now; many elements of which I find to be quite interesting. By the way, the answer is that all 100 blue eyed people leave on day 100.
If the number of days that blue eyed people remain on the island is greater than the number blue eyed people you see, you are the blue eyed person.
i'll bite...
ReplyDeletei think we can disregard 100 brown eyes for the time being since we know for a fact initially there is at least 1 blue eyed person. so we will deal with blue eyed ppl. first.
if b=1 by logic one person will leave the island on the first day simply because nobody else will leave the island. b(1) will be like oh shnaps i dont see any other blue and nobody else left time for me to bounce outta here.
if b=2 nobody will have left on the first day since b(1) and b(2) will have to wait and see if they are the only ones left from day 1. so they will leave on the second day when they realize nobody else is leaving.
if b=3 nobody will have left on the second day for the same reasons as b=2. so b(1) b(2) and b(3) are able to deduce that they are the only ones with blue eyes.
i dont think the setup changes at all until 100 days...
ku, can you solve this using maths?
I'm going to get to this eventually. I hope.
ReplyDeleteI'm still trying to write up an analysis on this, but it's hard xP. But here's the idea: the strategy for each scenario is built on the preceding strategy. So to continue on with what was given in the post, a 4 blue eyed person scenario would have one of the blue eyed person assume that the other 3 blue eyed people he sees are all of the blue eyed people that exist. Since he is a perfect logician and knows that the other 3 are are perfect logicians, he can safely assume that if there are only 3 blue eyed people on the island (and, so, they will each see 2), that they will leave on the third day using the strategy outlined above. This person will realize that when the remaining 3 blue eyed people did not leave on day 3, there must be 1 more blue eyed person which is the person himself. This thought process would be adopted by all 4 of the blue eyed people.
ReplyDeleteI'm still trying to work everything out in my head. I think I understand everything, but it's really hard to articulate.