The riddle
Randall Munroe (of xkcd fame) has, a bit hidden on his site, a logic puzzle:
A group of people with assorted eye colors live on an island. They are all perfect logicians -- if a conclusion can be logically deduced, they will do it instantly. No one knows the color of their eyes. Every night at midnight, a ferry stops at the island. Any islanders who have figured out the color of their own eyes then leave the island, and the rest stay. Everyone can see everyone else at all times and keeps a count of the number of people they see with each eye color (excluding themselves), but they cannot otherwise communicate. Everyone on the island knows all the rules in this paragraph.
On this island there are 100 blue-eyed people, 100 brown-eyed people, and the Guru (she happens to have green eyes). So any given blue-eyed person can see 100 people with brown eyes and 99 people with blue eyes (and one with green), but that does not tell him his own eye color; as far as he knows the totals could be 101 brown and 99 blue. Or 100 brown, 99 blue, and he could have red eyes.
The Guru is allowed to speak once (let's say at noon), on one day in all their endless years on the island. Standing before the islanders, she says the following:
"I can see someone who has blue eyes."
Who leaves the island, and on what night?
There are no mirrors or reflecting surfaces, nothing dumb. It is not a trick question, and the answer is logical. It doesn't depend on tricky wording or anyone lying or guessing, and it doesn't involve people doing something silly like creating a sign language or doing genetics. The Guru is not making eye contact with anyone in particular; she's simply saying "I count at least one blue-eyed person on this island who isn't me."
And lastly, the answer is not "no one leaves."
He admits the puzzle isn't his:
I didn't come up with the idea of this puzzle, but I've written and rewritten it over the the years to try to make a definitive version. The guy who told it to me originally was some dude on the street in Boston named Joel.
The answer
He gives his solution:
The answer is that on the 100th day, all 100 blue-eyed people will leave. It's pretty convoluted logic and it took me a while to believe the solution, but here's a rough guide to how to get there. Note -- while the text of the puzzle is very carefully worded to be as clear and unambiguous as possible (thanks to countless discussions with confused readers), this solution is pretty thrown-together. It's correct, but the explanation/wording might not be the best. If you're really confused by something, let me know.
If you consider the case of just one blue-eyed person on the island, you can show that he obviously leaves the first night, because he knows he's the only one the Guru could be talking about. He looks around and sees no one else, and knows he should leave. So: [THEOREM 1] If there is one blue-eyed person, he leaves the first night.
If there are two blue-eyed people, they will each look at the other. They will each realize that "if I don't have blue eyes [HYPOTHESIS 1], then that guy is the only blue-eyed person. And if he's the only person, by THEOREM 1 he will leave tonight." They each wait and see, and when neither of them leave the first night, each realizes "My HYPOTHESIS 1 was incorrect. I must have blue eyes." And each leaves the second night.
So: [THEOREM 2]: If there are two blue-eyed people on the island, they will each leave the 2nd night.
If there are three blue-eyed people, each one will look at the other two and go through a process similar to the one above. Each considers the two possibilities -- "I have blue eyes" or "I don't have blue eyes." He will know that if he doesn't have blue eyes, there are only two blue-eyed people on the island -- the two he sees. So he can wait two nights, and if no one leaves, he knows he must have blue eyes -- THEOREM 2 says that if he didn't, the other guys would have left. When he sees that they didn't, he knows his eyes are blue. All three of them are doing this same process, so they all figure it out on day 3 and leave.
This induction can continue all the way up to THEOREM 99, which each person on the island in the problem will of course know immediately. Then they'll each wait 99 days, see that the rest of the group hasn't gone anywhere, and on the 100th night, they all leave.
Before you email me to argue or question: This solution is correct. My explanation may not be the clearest, and it's very difficult to wrap your head around (at least, it was for me), but the facts of it are accurate. I've talked the problem over with many logic/math professors, worked through it with students, and analyzed from a number of different angles. The answer is correct and proven, even if my explanations aren't as clear as they could be.
User lolbifrons on reddit posted an inductive proof.
If you're satisfied with this answer, here are a couple questions that may force you to further explore the structure of the puzzle:
- What is the quantified piece of information that the Guru provides that each person did not already have?
- Each person knows, from the beginning, that there are no less than 99 blue-eyed people on the island. How, then, is considering the 1 and 2-person cases relevant, if they can all rule them out immediately as possibilities?
- Why do they have to wait 99 nights if, on the first 98 or so of these nights, they're simply verifying something that they already know?
These are just to give you something to think about if you enjoyed the main solution. They have answers, but please don't email me asking for them. They're meant to prompt thought on the solution, and each can be answered by considering the solution from the right angle, in the right terms. There's a different way to think of the solution involving hypotheticals inside hypotheticals, and it is much more concrete, if a little harder to discuss. But in it lies the key to answering the four questions above.
The question
Everybody on the island could have come to the conclusion that 'There is at least one person with blue eyes', simply by looking around, seeing 100 people with blue eyes, and realising that everybody can see at least one person with blue eyes.
So why is it necessary for the Guru to say 'I see at least one person with blue eyes' to get the ball rolling?
Answer
Let's continue the induction, since the jump to 99 blue eyes does seem weird. After all, everyone knows that someone has blue eyes.
If there are 4 blue eyed-people, A will look at B,C,D, thinking :
Maybe I don't have blue eyes (only 3 blue eyes?). In this case B must be thinking, that he may not have blue eyes either, and B is looking at C and D, whom he perceives as being the only ones to have blue eyes (since I consider the option that I don't have blue eyes), and B thinks that C is having the same reasoning. C thinks he does not have blue eyes and only D has.
Now, the issue here is that I, being A, can see that B has blue eyes. Therefore I know that C sees at least D and B as having blue eyes. But this is the reasoning of B, who does not know that he has blue eyes.
When I project myself into the reasoning of the next person, I cannot use the knowledge I have of their eyes color.
The same goes for 5 people and more. I see 4 blue-eyed people, each of which is possibly seeing only 3, and thinking that each of the other is possibly seeing only 2...
No comments:
Post a Comment