Saturday, February 16, 2008

On the difference between logic and clear thinking

Being a little teaser for the weekend.

Permit me to draw to your attention a marvellous CD called trees outside the academy by thurston (Moore of Sonic Youth). It's largely acoustic and quite melodic (in contrast to the frequently harsh electric noisery of SY); the songs are all interesting, and some are actually quite beautiful. Try it, you might like it.

A simple but infuriatingly tricky logic-puzzle meme is going around the Internets. Here's the short version courtesy of xkcd:
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 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?
The solution proposed by xkcd is here, and for what it's worth I think it is wrong because although his logic is correct, his solution does not address the question as it is stated in the problem. Spoiler warning: highlight the blank below this to read.

The logic depends on the number of blue-eyeds that can be seen by any given person. Let the number of blue-eyeds visible to a brown-eyed be N; the number visible to a blue-eyed is M (equal to N-1, because they cannot see themselves). This difference is the crux of the solution.

If I am the only blue-eye(N=1), then for me M=0. Therefore I must be the single blue-eye whom the Guru saw, and must leave immediately on day zero (N-1).

If there were only two people on the island, one blue-eyed person and one brown-eyed (also N=1), the same thing would happen: The blue-eyed would see the brown-eyed and realize that their own eyes must be blue, and leave immediately on day zero (N-1).

What if there were only two people on the island, both blue-eyed (but neither knows his or her own colour)? N=2. In this case they would look at each other and think, "s/he over there is the person the Guru meant" and not leave. Next day, seeing that the other person had not left, they would both think "s/he did not leave, meaning that s/he thinks that I am the person the Guru meant, therefore I have blue eyes." Both would leave on day one (N-1).

If there were four people on the island, split two and two (N=2), the situation is more complex but not different. The browns see two blues; each blue sees only one, thinks "s/he was seen by the Guru" and so remains. On day one, each blue still sees a blue and therefore thinks "aha, s/he thinks that the Guru meant me", knows that s/he is blue-eyed, so both blues will leave. Meanwhile, what are the browns thinking? On the morning of day one, they see two blues leave, know that they must have seen only one other, and know therefore that their own eyes are not blue.

The solution is thus: Given that I see M blue-eyed people, wait to see what happens M-1 days after the Guru spoke. If the blue-eyeds leave on day M-1, then my eyes must be brown. If I can still see blue-eyeds on day M, then my eyes are blue too and I will leave, with the others, on the next day.

However: the problem states that anyone arriving at knowledge of his or her eye colour must leave the island, not that persons discovering themselves to be blue-eyed must leave. The true answer is that almost everyone will leave, except those having a colour that occurred exactly once in the original population.

What happens next is a repeat of the blue-eyed scenario: the not-blues look around and see at least one other eye colour. Say that there are six greens, of which I see M examples. if they leave on day M-1, then my eyes are not green. I may remain on the island—for now—because I still do not know my eye colour, just that it is neither blue nor green. If they are still present, then my eyes too are green and we must all leave.

Labels: , ,


Blogger zhoen said...

On day one, I would say I had blue eyes. If I was not taken off the island, the next day I would say I had brown eyes, and would be taken off. Either way, surrounded by people who make life too complicated, I would probably just swim off to get away from them. If I were the Guru, I'd just tell everyone what color their eyes were, and have the whole place to myself immediately.

February 16, 2008 at 4:18:00 PM GMT+1  
Blogger JoeinVegas said...

Zhoen has the best suggestion for the Guru - get rid of the idiots. But I disagree with your hypothesis. Once the number of blue eyes grows sufficiently large that an individual cannot count the logic then there is no way anyone could tell. Any individual would look out and say yes, there are people with blue eyes. There still is no logical way to determine your color from that. (or am I really too thick?)

February 17, 2008 at 6:38:00 AM GMT+1  
Blogger Udge said...

A normal, healthy human would of course say "The Guru sees at least one blue-eyed person? Well, so do I. What's for lunch?"

I think that this puzzle perfectly illustrates the difference between logical deduction and clear thinking (as indeed was its title). No human being would act in that way; or rather: an assembly of logicians large enough to enact the puzzle in real life would long since have descended into madness and bloodshed.

Joe, you are quite right that the solution requires that all islanders can see and correctly count each other all the time, and that they can remember the results over a span of half a year. Quite absurd, really, but such is (apparently) the Weltanschauung of logicians.

It took me the whole of Saturday morning to work this out, and I only really grokked it after reading xkcd's solution. I had to make up a little chart of people and eyes and days and work through a few examples to grasp how it worked—in this impossible perfectly-selected population.

February 17, 2008 at 10:12:00 AM GMT+1  
Blogger CarpeDM said...

Um, if it's really cool island, why would you care what color your eyes are?

I've mentioned I'm not very logical right?

February 23, 2008 at 11:39:00 AM GMT+1  

Post a Comment

<< Home