September 25, 2007

Blue Eyes

I have been thinking about this all evening.

Have you had time to read and reflect on this weird little logic puzzle? Or do you not care if I end up spoiling it? Then read on.

UPDATE: SPOILER!

First off, after 20 minutes of giving it some focused thought, I still find myself wondering, "Will the answer be satisfying?" I know I shouldn't! But hey: a few times in my reasoning about the puzzle I came across a "solution" that involved shifting the problem from one of certitude to one of probability (Monty Hall) or sneaking in some extra divulgation (blindness... ugh! no good!). No, I trust the xkcd guy to have an impregnable, unimpugnable answer.

I just don't see how the information imparted by the Guru can have any impact on blue-eyed people or brown-eyed people or the one green-eyed person. I just don't see how anybody in any position could use this data to deduce his own eye color.

Let's try reducing the problem to three or four people. If there's a blue-eyed, a brown-eyed, and a green-eyed guru, then the guru saying "I can see someone who has blue eyes" would tell the blue-eyed person the color of their eyes. Obvious. Now let's add just one person: another blue-eyed person. Let's say you are that blue-eyed newcomer. The guru says there is a person with blue eyes, and you see a person with blue eyes, a person with green eyes, and a person with brown eyes. Nothing tells you your eyes are blue or brown or green or anything. So you don't leave. Does the fact that neither of the blue-eyes leaves make it easier for anybody to guess their color the next day? The blues both stayed. So each blue knows the other one didn't leave because there was another blue. So bingo, both blues leave the next day. Now add a third blue. This doesn't work any more, does it? Or does it recurse? If the first two blues didn't leave the second day, then that means there has to be another blue... All three blues leave the third day. Woah, I have to make sure I don't trip myself up with the slightly diachronic way I am bringing on these blue protagonists. The conclusion is the same if everyone is there from the start. Uh, is it? Anyway, I don't see it recursing to 5 or 6, let alone 100... Hm. Wait a minute. I think it might, though proving it rigorously sounds like it could make my head hurt. Ah, but there's still a little knot: why do the browns not each individually have the same reaction? Just a minute. It's because there's one fewer actual blues than the number of putative blues as seen through the eyes of a brown or green who considers the possibility that he or she is blue. So if those 100 blues don't leave on the 100th night, then every brown will be entitled to think that they are the 101st blue. Yep, I think that's it. A bit fuzzy around the middle, but I think I nailed it.

Posted by Erik at September 25, 2007 11:32 PM
Comments

I will first look at the puzzle and try to solve it. So I'm commenting without reading your post, the opposite of the more usual reading without commenting :-)

Posted by: Kai Carver at September 26, 2007 12:10 PM

Augh! I fell for your trap! I believe I'm well on my way to solving the puzzle. HOWEVER, I spent way more time reading this, this, and this. Electric skateboards? Stallman gets a katana? "Wanting something makes it real"? You people live in a land of magic. I updated my feeds. Some day I'll never miss a thing. Still haven't read your post, by the way.

Posted by: Kai Carver at September 27, 2007 03:25 AM

Over dinner last night with two math professors / yoga partners, one brought up a similar puzzle:


An order of perfectly logical monks lives isolated in their monastery. They are sworn not to communicate with each other in any way. They have no mirrors, and no other means by which a monk can see his own face. They see each other only once each day when they all gather together for afternoon prayers.

There is a demon loose in the land - the relativity demon. If a person becomes possessed by this demon, the demon's sign (e=mc2) appears on his forehead. The monks know that this is a very powerful demon -- one that can never be exorcised -- and so, if a monk would discover that he bore this mark, that evening, in the privacy of his cell, he would commit suicide.

One afternoon, a visitor (one who is not sworn to silence) comes to the prayer meeting. He looks around the room, announces "At least one monk in this room has the demon's mark on his forehead", and immediately leaves. The monks all look around, examining each other's foreheads. Nothing unusual happens that evening.

At the second day's prayer meeting the monks all look at each other, but again that evening nothing unusual occurs.

...and so on for the third, fourth, fifth, and sixth days.

But on the seventh evening, all the monks commit suicide.


What happened? How many monks were there? How many had the demon's mark?


(copied from "gnome"'s post at Physics Forums)


I like this one because it's funny. Poor monks!


I think I ran across these puzzles years ago when I was reading fun books by Hofstadter, Gardner, and Smullyan instead of doing my assigned problem sets. Good times.

Posted by: Kai Carver at October 10, 2007 06:53 AM

A sad thing about those monks is that, in all the time before the visitor came, each of them had to live with the fact that everyone else was possessed by the demon. You'd hope that, in addition to being perfectly logical, they had no notion of probabilities, and no self-doubt. Otherwise, realization and suicide must have come as a kind of immense relief.


Another variation on these "I know that he knows" puzzles mentioned last night is the cuckolds of Baghdad (French).

In what looks like a fun and dishy book (French version), logician Jean-Yves Girard calls these puzzles infantile, and suggests a variation, "the cuckolds of Houston", involving two men: V, who is an epistemic logic PhD, and W, who's just a moron. The story ends very sadly for V's wife.

(That's sort of what Erik alludes to at the end of his post. What if the blue-eyes are morons? The next day, all the (smart) brown-eyes leave the island, and the blues are left feeling smug.)


Girard seems like an interesting guy. He gave an entertaining talk on mathematical foundations (French) at the Universit� de tous les savoirs in 2000. Among other things, he argues foundationalists are like the Dupondt brothers lost in the desert in "Tintin au pays de l'or noir". And his paper Locus solum: from the rules of logic to the logic of rules, in which he defines something called ludics, contains an amusing mathematical Devil's Dictionary. For example:

Trinity
A ∧ B is true when A is true and B is true. ∧ is the Syntax, "and" is the Semantics, and since you could imagine that there is nothing in this definition, comes the Meta : and is not quite ∧, it is meta-∧... Just like the Christian God comes as three-in-one, Logic has its own Trinity, namely Semantics (the Father), Syntax (the Son or Verb), and Meta (the Holy Ghost). Many logical papers look like a religious service.
See : Black Mass, Completeness (external), Jurassic Park, Meta, Schizophrenia, Syntax, Semantics.

Posted by: Kai Carver at October 10, 2007 11:18 AM

A yogamathbeer topic this week was the "lonely runner" conjecture. J�r�me said he'd been working on it. It's been proven for up to 7 runners. When I later looked it up, I was impressed to find he's cited for his simplified proof of the k=6 case. I haven't tried to understand it, as I'm just happy to know it's been proven. On to k=8! Come on, guys, how hard can it be? Just one more runner and you can't prove it anymore? What's the deal?

Posted by: Kai Carver at October 25, 2007 03:44 AM
Post a comment












Remember personal info?