Here's one to aggravate you all..
http://xkcd.com/blue_eyes.html
If you've actually come across this puzzle and actually know the solution, don't post it. But DO post if there's something wrong with that description of it.
Because after listening to my friend's solution (he was the one who sent me the link), we later realized it was flawed. Moreover, I've made several deductions which are making it seem impossible. I'll list them in a bit behind a cut. Basically, since the xkcd guy isn't the original author but asserts that a straight solution is possible, I think he may have misphrased or miscommunicated some crucial fact.
BTW, there's been a common solution, but I think it's actually.. too simplistic. Be careful not to click if you want to try to work either it or a fully rigorous solution (presuming they're even different).
The Proposed Solution
This is actually simpler than I expected it to be for the problem:
It's a proof by induction (a base case and the general case).
If there were only 1 Blue-Eyed islander, he would immediately know it and leave the first night.
If there were 2 Blue-Eyeds, they would each expect the other to leave the first night. The next day, they would see that they hadn't, each realize they were also a Blue, and both leave the 2nd night.
If there were 3 Blue-Eyeds, all 3 would leave the 3rd night.
...
Because there are 100 Blue-Eyeds, all 100 would all leave the 100th night.
Now at first that sounds all fine and clever, but then we get to the question of whether the Brown-Eyeds or the Guru leave. At least another version of this induction proof I saw out there suggested that they both remain, but there's a problem with that.
Flaws with the Induction Proof
Here are the deductions:
Deduction #1: The Guru's statement imparts no new information. The statement can only impart new information to the islanders if there exists at least one islander who CAN'T see a Blue-Eyed. But given the initial conditions, EVERY islander can see someone with blue eyes. Moreover, every islander knows that all the others can see someone with blue eyes. Hence "everyone can see someone with blue eyes" is already in every islander's knowledge base. This is pretty much everyone thinking: "Yes, we KNOW you can see someone with blue eyes because we can ALL see at least one person with blue eyes!"
Deduction #2: If the above is true (Guru's statement is redundant), and if they are capable of leaving (as the xkcd author asserts), then the Blue-Eyeds must be able to eventually do so without her statement.
Deduction #3: If the Blue-Eyeds can eventually leave by their own reasoning, then the Brown-Eyeds can do the same for their own group. They are in the same circumstances (and they do not even need to know that there just happen to be the exact same number of either). So they know that every islander can see someone with brown eyes as well.
Deduction #4: The departures of either group are mutually independent. Because there are more than 2 eye colors, Not Blue does not imply Brown.
Deduction #5: If either of the groups can leave, they both must eventually leave after the same amount of time on the same night. One group does not even leave before the other group, because the above two deductions circumvent the fallacy of the excluded middle. Only one of the two main groups can leave first. The Blues cannot identify their own eye colors by the 100th day if the Browns are attempting to do the same. The islanders must tacitly agree to begin self-identifying by one color first (probably Blue, based on the Guru's statement).
Deduction #6: All the islanders know Deduction #1, because they all know it is impossible for there to be an islander who can't see a Blue. Likewise, it is impossible for there to be any islander who can't see a Brown.
Deduction #7: In fact, all the islanders know all these Deductions. They are perfect Logicians and each has the information necessary to reach these conclusions.
Now the problem with the induction proof is that I suspect the base case may not actually extend to the general case. But I don't know how to prove that it does or doesn't. I think it involves Deduction #1. In order for the Guru's statement to impart new information to at least someone in the entire group, there must exist an islander who cannot see a Blue. The only case where that's possible is if there's only 1 Blue. If there's more than 1 Blue, no one in the group learns anything new from her statement. Thus, I have this feeling that the xkcd author has somehow misstated the problem or one of its constraints.
So I guess the question is: Can any of the islanders figure out their eye color without the Guru's statement? The wild thing is that I think they have to be able to. Because all the islanders are perfect logicians, they would all have instantly figured out the Guru's statement without her ever making it. So both the Blues AND the Browns would have to all leave on the 100th night and the Guru is left alone forever. First, the Blues identify themselves by the 100th night and leave. Then, the Browns must repeat the entire process (in order to confirm that none of them are an odd man out from the 99 other Browns) and leave on the 200th night. The Guru is left alone on the island forever, knowing only she is neither Blue nor Brown.
If you've actually come across this puzzle and actually know the solution, don't post it. But DO post if there's something wrong with that description of it.
Because after listening to my friend's solution (he was the one who sent me the link), we later realized it was flawed. Moreover, I've made several deductions which are making it seem impossible. I'll list them in a bit behind a cut. Basically, since the xkcd guy isn't the original author but asserts that a straight solution is possible, I think he may have misphrased or miscommunicated some crucial fact.
BTW, there's been a common solution, but I think it's actually.. too simplistic. Be careful not to click if you want to try to work either it or a fully rigorous solution (presuming they're even different).
The Proposed Solution
This is actually simpler than I expected it to be for the problem:
It's a proof by induction (a base case and the general case).
If there were only 1 Blue-Eyed islander, he would immediately know it and leave the first night.
If there were 2 Blue-Eyeds, they would each expect the other to leave the first night. The next day, they would see that they hadn't, each realize they were also a Blue, and both leave the 2nd night.
If there were 3 Blue-Eyeds, all 3 would leave the 3rd night.
...
Because there are 100 Blue-Eyeds, all 100 would all leave the 100th night.
Now at first that sounds all fine and clever, but then we get to the question of whether the Brown-Eyeds or the Guru leave. At least another version of this induction proof I saw out there suggested that they both remain, but there's a problem with that.
Flaws with the Induction Proof
Here are the deductions:
Deduction #1: The Guru's statement imparts no new information. The statement can only impart new information to the islanders if there exists at least one islander who CAN'T see a Blue-Eyed. But given the initial conditions, EVERY islander can see someone with blue eyes. Moreover, every islander knows that all the others can see someone with blue eyes. Hence "everyone can see someone with blue eyes" is already in every islander's knowledge base. This is pretty much everyone thinking: "Yes, we KNOW you can see someone with blue eyes because we can ALL see at least one person with blue eyes!"
Deduction #2: If the above is true (Guru's statement is redundant), and if they are capable of leaving (as the xkcd author asserts), then the Blue-Eyeds must be able to eventually do so without her statement.
Deduction #3: If the Blue-Eyeds can eventually leave by their own reasoning, then the Brown-Eyeds can do the same for their own group. They are in the same circumstances (and they do not even need to know that there just happen to be the exact same number of either). So they know that every islander can see someone with brown eyes as well.
Deduction #4: The departures of either group are mutually independent. Because there are more than 2 eye colors, Not Blue does not imply Brown.
Deduction #5: If either of the groups can leave, they both must eventually leave after the same amount of time on the same night. One group does not even leave before the other group, because the above two deductions circumvent the fallacy of the excluded middle. Only one of the two main groups can leave first. The Blues cannot identify their own eye colors by the 100th day if the Browns are attempting to do the same. The islanders must tacitly agree to begin self-identifying by one color first (probably Blue, based on the Guru's statement).
Deduction #6: All the islanders know Deduction #1, because they all know it is impossible for there to be an islander who can't see a Blue. Likewise, it is impossible for there to be any islander who can't see a Brown.
Deduction #7: In fact, all the islanders know all these Deductions. They are perfect Logicians and each has the information necessary to reach these conclusions.
Now the problem with the induction proof is that I suspect the base case may not actually extend to the general case. But I don't know how to prove that it does or doesn't. I think it involves Deduction #1. In order for the Guru's statement to impart new information to at least someone in the entire group, there must exist an islander who cannot see a Blue. The only case where that's possible is if there's only 1 Blue. If there's more than 1 Blue, no one in the group learns anything new from her statement. Thus, I have this feeling that the xkcd author has somehow misstated the problem or one of its constraints.
So I guess the question is: Can any of the islanders figure out their eye color without the Guru's statement? The wild thing is that I think they have to be able to. Because all the islanders are perfect logicians, they would all have instantly figured out the Guru's statement without her ever making it. So both the Blues AND the Browns would have to all leave on the 100th night and the Guru is left alone forever. First, the Blues identify themselves by the 100th night and leave. Then, the Browns must repeat the entire process (in order to confirm that none of them are an odd man out from the 99 other Browns) and leave on the 200th night. The Guru is left alone on the island forever, knowing only she is neither Blue nor Brown.