Blessed by the Potato

I ran into this logic puzzle the other day, and have been thinking about it a lot between Nyquil comas. I will try to explain it as best I can here, but be warned that there are pages of discussion and argument on this as people try to wrap their brains around it. If you want to think about it on your own for a while, then stop reading here.

So, to start with, I’m going to drop the numbers down from what is presented on the xkcd page: let’s say there are 20 people in this weird tribe of logicians, and 5 of them have blue eyes. This better matches the forum discussion, and makes the numbers easier to follow.

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. If anyone has figured out the color of their own eyes, they [must] leave the island that midnight. 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 5 blue-eyed people, 15 brown-eyed people, and the Guru (she happens to have green eyes). So any given blue-eyed person can see 15 people with brown eyes and 4 people with blue eyes (and one with green), but that does not tell him his own eye color; it could be 16 brown and 4 blue. Or 15 brown, 4 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?

The answer, [Spoilers!] to start with, is that the blue eyed people would all leave the island together on the 5th night.

The logic looks inductive: if there was one person with blue eyes, they would see a sea of brown eyes, and the gurus words would speak to him, and him alone: he does not see anyone with blue eyes, so therefore he must be the one with blue eyes the guru was speaking about; he would leave the first night. If no one leaves the first night, then everyone knows that everyone else saw at least one other person with blue eyes, so they could not conclude that they were the only one and leave. If there is anyone who only sees one person with blue eyes, then they know that they must also have blue eyes, because otherwise that lone blue eyed person would have left (i.e.: the blue eyed person must have seen someone else with blue eyes, namely them). For every extra blue eyed person, the departure date is delayed one day. If no one left the second night, then there must be three blue eyed people, so anyone who only saw two blued eyed people would leave on the third night.

There are then a few more questions. The first: what information did the guru really add? The guru made it so that not only did everyone see people with blue eyes, she made it so everyone knew everyone knew that there were blue eyes.

The logic proceeds thusly: A person with blue eyes (say #5) sees 4 other people with blue eyes, but may assume that they have brown eyes. So #5 thinks that #4 sees 3 other people with blue eyes, and thinks that #4 thinks #3 sees 2 others; #5 thinks that #4 thinks that #3 thinks that #2 only sees one other, and thus #5 thinks that #4 thinks that #3 thinks that #2 thinks that #1 sees only brown eyed logicians.

The chain of logic is absolutely insane, since #5 knows, directly, that each of #’s 1-4 must see at least 3 others, because he can see all 4 of them. But nonetheless, he knows that each makes those assumptions down the chain. The trick is that at the end of the chain, someone thinks that someone only sees brown, which doesn’t help them guess their eye colour, since they don’t necessarily know that there is at least one blue present [or rather, they don’t think that someone else thinks that they think that they know… ok, it’s making my head hurt follow those chains of reasoning]. Once the guru speaks up, everyone knows that everyone at the bottom of their chains of reasoning knows that blue exists, and thus would deduce their eye colour if the twisted logic played out. It starts the countdown so that by day five, the 5 blue eyed people up and board the ferry.

It really makes my head spin to try to follow all that, especially since I sometimes have problem with the “a pencil” problems to begin with. But here’s the thing that I wonder: following the chain of logic, you know that if no one leaves the first night, it means that the blue eyed people all saw at least one other blue eyed person. Following the chain of guessing what you think the next guy thinks the next guy thinks, you get to the point where the last person hanging in that chain might think they were the only ones and actually leave the first night. So if no one does, that’s new information to act on. But, you also know, in addition to the crazy deduction, that everyone else sees at least one other blue. So no one expects anyone to leave that first night; in that case, is the fact that no one does leave actually new information? Does the chain of reason really continue night after night until they call all leave on the fifth? In fact, with 5 blues there are enough that you can know that not only does everyone else see at least one other blue, but you can know that they know everyone else can see at least one other. Can you move to the next step of waiting for someone to leave on day 4 if you knew nothing would ever happen on day 1?