Logic/Induction

[just_you_wait]

Problem: 1000 perfect logicians are imprisoned. 500 have blue eyes, 499 people have brown eyes, and one has green eyes. They can see each other's eyes but not their own, and cannot communicate eye colors to each other. At the end of every day, those who have deduced their own eye color are freed. The guard states, "At least one of you has blue eyes

Comments

[jackbishop]

The knowledge they gain is actually quite deeply embedded: if there were one blue-eyed person, the crucial information they gain is indeed that someone has blue eyes (and since it's nobody else, it's them). If there were two, then as you point out, they already know someone has blue eyes, but the crucial information they gain is the knowledge that both of them now know that somebody has blue eyes (which they didn't know before -- I, with blue eyes, might look at another blue-eyed person, the only one I can see and say "oh, he doesn't know his eye color because he doesn't know blue-eyed people exist."). Likewise, if there were three blue-eyed people, then everybody knows that somebody has blue eyes, and everybody knows that everybody knows that someone has blue eyes (even a blue-eyed person might note that since there are at least two blue-eyed people, each of them sees some blue eyes), but everybody doesn't know that everybody knows that everybody knows that someone has blue eyes -- until they're told, at which point they learn this

[just_you_wait]

But in the three blue-eyed case, isn't the fact that everybody knows that everybody knows that there is at least one blue-eyed person sufficient to begin the logical chain?

[physics_dude]

The full reasoning is counterfactual. Suppose n people have blue eyes. Their reasoning goes like this:

I see n-1. If I'm not blue, each of them sees n-2, and reasons:
I see n-2. If I'm not blue, each of them sees n-3, and reasons:
...
I see 1. If I'm not blue, they see 0, and would know and leave on day 1.
Since they didn't leave on day 1, I'm blue and can leave on day 2.
...
Since they didn't leave on day n-1, I know I'm blue and can leave on day n.

Each of the "If I'm not blue..." is a counterfactual hypothesis that is eventually proven false, by contrapositive, when something it implies is proven false. The statement "n>=1" does not provide new information when n>2, but it would have provided new information in the deeply nested counterfactual universe where n=1, which is required to start the induction.

[just_you_wait]

That was incredibly clear and concise. Many thanks!

Edited to add: "Deeply Nested Counterfactual Universe" would be a great band or tumblr name.

[notmrgarrison]

I think this is wrong.

Suppose there are 5 people with blue eyes.
At the beginning of day 1 they can easily determine that regardless of their own eye color, no one else is going to leave at the end of the day, so when no one leaves on day 1 they learn absolutely nothing that they didn't already know.

[physics_dude]

I agree, nobody learns anything on day one. They learn on day 5.

From an information theoretic perspective, I believe they are getting one bit of information each day after day 1. Specifically, whether or not the blue eyed people left. Moreover, once they leave, that's it. So whatever information they're getting over time, they're getting as unary.

Everyone with blue eyes knows on day one the value is either 4 or 5. After day 4, they see the others didn't leave, and rule out 4. If there were actually 4, the guard's statement would have been necessary for them to leave on day 4, from the induction. So the statement, combined with the blue eyes not leaving, yields new information after day 4.

I don't claim to understand this intuitively. I struggled and failed to approach it informally. I eventually reached my conclusions by translating from a more formal analysis. I am 99% certain of what I've said, but only because it agrees with the formal analysis.

[notmrgarrison]

I wrote a proof below that makes sense to me, but, it's not really a mathematical proof, it just looks like one. I don't see what's wrong with it, but I'm not convinced it's right.

Have you seen this problem on a forum with a lot of smart people?.
(Even that doesn't settle it, as the Monty Hall Problem showed very smart people can get things wrong).

[physics_dude]

What proof? Or do you mean in a different comment?

This was in xkcd and the solution page has a link to a formal proof on reddit.
http://xkcd.com/solution.html
http://www.reddit.com/r/AskReddit/comments/khhpl/reddit_what_is_your_favorite_riddle/c2kdlr6

I don't think the reddit proof is quite complete though. Where it claims to be showing F(n+1)=G(n+1) I think it is really showing F(n+1) <= G(n+1). (I don't get the choice of notation; I'd just say F(n+1)=n+1, where F maps from the number of people to the day they leave on.) To be complete it needs equality, i.e. you need to argue that if n+1 people have blue eyes, they can't leave _before_ day n+1.

[physics_dude]

I tried to post a reply with links and apparently it's considered spam.

I'm not sure what proof you're referring to. If you look for the solution to this problem on xkcd, though, that has a link to a "formal" proof on reddit. It doesn't really define what it's talking about though, and where it says "F(n) = G(n)" for "if there are n people with blue eyes they leave on day n" it should probably just say "F(n) = n" where F maps from count to day. I think it's incomplete because I think it shows F(n) <= n, not F(n) = n.

[just_you_wait]

(I unspammed it for you.)

Whoa, I didn't know it was on xkcd/reddit years ago. One of my friends posted it on facebook, along with some other math/logic puzzles.