Wow, thanks for that doozey of a puzzle! (and more importantly, for the solution, without which I wouldn't have "solved" :P the puzzle)
Some people have suggested that on day 101 the brown-eyed people would all leave, but that is impossible. Below is my explanation, as well as my analysis of other potential holes/redundancies (which may well be intentional, so I'll just call them "quirks").
If I made an error (including spelling or formatting), please pm me or reply and I'll edit this post so it is clearer. I used the male gender because it's complex enough already.
BROWN-EYED PEOPLE CAN'T LEAVE:
After the blue-eyed people leave, it's not possible for any brown-eyed person to deduce that their eyes are brown without a second statement from the Guru, no matter how long they wait. This is because to each person, his or her eyes can either be brown or not-brown (-and-not-blue). Even though there are no longer any blue-eyed people around, it doesn't matter. If they could figure it out by only seeing 99 other brown-eyed people, then the blue-eyed people could have done it without the Guru's statement, which is key in closing the inductive loop (see below).
ALTERNATE WAY OF THINKING ABOUT THE BROWN-EYES:
This puzzle, and the inductive reasoning behind it, makes much more sense if you treat each person individually, rather than as a group with similar characteristics, even though they are all interchangeable. Let's name them X~001, X~002, ... , X~099, and X~100 (much to the dismay of their parents). In addition, the brown-eyed people have no more information on day 100 than they did on day 1. So I'll count the brown-eyed problem from day 100, not day 200.
For X~100 to know on day 100 that his eyes are brown, he would have to observe the 99 brown-eyed people he sees not
leave on day 99. However, person X~099 doesn't know his own eye colour, and X~100 knows that X~099 doesn't know his own (X~099's) eye colour.
As far as X~100 is concerned, X~099 would leave on day 99 only if X~100 was not
brown-eyed, and if the 98 brown-eyed people that X~099 sees did not
leave on day 99. However, person X~098 doesn't know his own eye colour, and both X~100 and X~099 know that X~098 doesn't know his own eye colour. This repeats until we get to X~001, where, as far as X~100's hypothesis-within-a-hypothesis-times-100 is concerned, nobody knows their own eye colour (or, people are only logically aware of the eye colour of people with smaller-number names).
The crux is twofold:
- Each brown-eyed person plays this situation out in their minds with themself
as person X~100
- Each brown-eyed person X~100 knows that even though he sees 99 other brown-eyed people, he doesn't know whether those people see 99 other brown-eyed people (if X~100 is brown-eyed) or 98 brown-eyed people (if X~100 isn't brown-eyed).
(this is where I get a bit fuzzy on the logic)
Therefore, Person X~100 knows that person X~099's knowledge of his own eye colour depends on person X~098's knowledge of his own eye colour ... which depends on person X~002's knowledge of his own eye colour, which depends on person X~001's knowledge of his own eye colour, which person X~001 simply cannot know*. That is why the brown-eyed people cannot know their own eye colour.
However, the blue-eyed people, who go through the exact same logic process, know that for each blue-eyed person playing the role of X~100 in his own mind, there exists at least one X~001 whose eyes are blue. Because of the Guru's statement, this hypothetical X~001 can be assumed to know his eyes are blue on the first day (even though this one person can actually be any of the 99 or 100 people who have blue eyes, as far as X~100 is concerned). X~100 knows that if on day one that person X~001 doesn't leave, then person X~002 will have figured out his eye colour (because persons X~003 to X~100 haven't figured out their own eye colour according to the hypothesis). If on day two persons X~001 and X~002 don't leave, then person X~003 would know his eye colour.
Although it seems obvious that nobody will leave on the third day, since X~100 knows that there are at least 99 people with blue eyes, it becomes necessary to follow this process to the 99th day, because X~100 doesn't know his own
eye colour. Even though each person plays out the situation as X~100, they know that if their eyes are also blue, they could just as well be somebody else's hypothetical person X~001 or X~099.
[* Especially if it depends on the Guru knowing her own eye colour :P]
It's possible that Randall overlooked these points, but it is equally possible that he decided to leave them in after careful consideration.
the puzzle wrote:1. A group of people live on an island. They are all perfect logicians -- if a conclusion can be logically deduced, they will do it instantly.
2. No one knows the color of their eyes.
3. Every night at midnight, a ferry stops at the island. If anyone has figured out the color of their own eyes, they [must] leave the island that midnight.
4. On this island live 100 blue-eyed people, 100 brown-eyed people, and the Guru.
5a. The Guru has green eyes,
5b. ...and does not know her own eye color either.
6a. Everyone on the island knows the rules and the properties stated above
6b. ...(except that they are not given the total numbers of each eye color)
6c. ...and is constantly aware of everyone else's eye color. Everyone keeps a constant count of the total number they see of each (excluding themselves).
7. However, they cannot otherwise communicate.
8a. So any given blue-eyed person can see 100 people with brown eyes and 99 people with blue eyes, but that does not tell them their own eye color; it could be 101 brown and 99 blue. Or
8b. 100 brown, 99 blue, and the one could have red eyes.
Unitalicized sentences/clauses are not contentious to the problem of brown-eyed people leaving.
Sentence 2's quirk is a mere editing point on technicality. They don't know their eye colour to start
, but the blue-eyed people will be able to deduce it, and arguably "know" their own eye colour. I think it can be combined with clause 5b; see comments two paragraphs down. Also, I'd clarify by saying they don't know the colour of their own
In Sentence 3 (actually two sentences), I would replace "figured out" with "deduced", and "they [must] leave" to something more like "they can and will leave." There seems to be no mechanism for them to prove that they know, other than the fact that they are perfectly logical, which has been stated.
Sentences 4-8 are quirky. Specifically, sentence 4 and clause 5a are quirky because of the quirk in clause 6a, but is implicitly (though quirkily) unquirked by clause 8b. Um... I meant that seriously. See next paragraph.
The quirks lie in how much each person knows about eye colour. Sentence 6 doesn't clearly state how much information is retained regarding eye colours after clause 6b is factored out. It tends to imply that the islanders know the only eye colours are blue and brown (and green). Sentence 8b clarifies this, but if sentences 4-6 were clearer, sentence 8 could be unnecessary.
Specific rules that need mentioning in sentences 4-8 are:
- Eye colours include blue, brown, and green.
- Eye colours do not necessarily exclude any other colour
- Sentence 6c: Everyone on the island is aware of everyone else's eye colour, and keeps a constant count (also a red herring, as it implies that some islanders may leave before/after others--good one!) of the number they see of each (excluding themselves).
- None of the islanders--not even the Guru--knows his or her own eye colour (implied from this is that they don't know exactly how many people of each eye colour there are)
- Nobody on the island can communicate another's eye colour in any way.
- Everyone knows the above rules
- There are 100 blue-eyed islanders, 100 brown-eyed islanders, and the guru, whose eyes are green.
Another quirk with sentence 5 is that the guru's eye colour doesn't matter at all. If her eyes were blue, everyone would know that, and the other blue-eyed people would leave in no lesser or greater number of days; if her eyes were not blue, well we know the solution to that. Stylistically, it provides an explanation for why she is the one person who gets to speak, and adds another variable for the solver to consider. However, I think Randall is being generous: the title to the "hardest logic puzzle in the world" would go to this puzzle, but with the guru's eye colour left vague to the reader (but clearly not a member of the original 200). For this reason, the Guru can never leave.
A quirk throughout is that the inhabitants (except for the Guru) are always referred to in the plural form (likely to avoid copious repetitions of "he and she" while remaining ...Hold on, I think I swallowed a gerbil. Okay. What was I saying?, or otherwose choosing between calling them all males or all females). This adds to the difficulty because the inductive reasoning requires you to think of the situation from the individual's standpoint. Sentence 8 relieves this difficulty a bit, and could be removed if the points that it addresses are clarified.
I think the timing should be changed and clarified, in such a way that the guru makes his claim on the first day, before
the ship comes (dawn and dusk; noon and midnight; 2:40 and 4:20; it doesn't matter). This way, it is clear for the purposes of confirming the answer to denote when the "100th day" comes in relation to the day the guru makes his statement.
...Since Randall is the author of the puzzle, I will leave it to him to decide whether to incorporate any of these suggestions in future versions of his puzzle. Either way, I wouldn't have been able to solve it on my own.
...Also, as a clarification, I don't usually use the word "quirk" in my day-to-tday life, I just wanted to avoid calling them "problems", "unclarities", "weaknesses," or "inefficiencies," because they are not necessarily so.
...Also, this post took me four hours to write. Phew!