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

[notmrgarrison]

How would they know their eyes weren't green?

[just_you_wait]

By induction, which I'm not sure holds. (Not sure who you're referring to by "they", so I'm guessing someone with brown eyes.) If their eyes were green, the browns would have left the day prior.

[notmrgarrison]

The people with brown eyes. As far as I can see, you have blue and not blue. How could any non-blue-eyed person know what color their eyes were?

[just_you_wait]

Since everyone can see at least two people with brown eyes, everyone knows that everyone else knows that there is at least one person with brown eyes, which I think is sufficient to form the base case for induction. If there were a color group with only one or two members, they would not be able to deduce their own color.

[leliel]

Is there any penalty for guessing wrong?

If not, everyone's free by the end of the 3rd day... ;p

I don't see how anyone knows what color their eyes are unless they see all of the others, which doesn't seem practical at a 1000 population level...

But anyways, on your 499th day, how do your browns know they aren't green?

[just_you_wait]

Presumably they're not allowed to guess; they either know their eye color or they don't.

Ok, suppose 10 blues, 9 browns, 1 green for practical purposes.

So each original brown sees 498 browns, and isn't sure if there are 498 browns and he's not brown, or if he is brown and there are 499 browns. If, after the 498th day, the 498 browns he can see haven't left, he knows he's a brown. The induction hinges on establishing the base case, and I'm unsure as to whether or not it holds.

[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]

Another way of looking at this:

Suppose you have 2 people both with blue eyes, and however many non-blue eyed people.
After day 1, neither blue left, so both realize (by assuming they were brown and then not seeing the other guy leave) that they must have blue eyes, and leave on day 2.

Now suppose you have 3 people with blue eyes, and you're one of them.
You assume your eyes aren't blue, and observe that the other two blue guys didn't leave on day 2 like the previous example, so on day 3 you realize you're blue too, and you all leave on day three.

Now suppose you have n+1 people with blue eyes, and you're one of them.
You assume your eyes aren't blue, and observe that the other n blue guys didn't leave on day n like the previous example, so on day n+1 you realize you're blue too, and you all leave on day n+1.

[notmrgarrison]

I think this is wrong.

Your assumption that your eyes aren't blue only holds in your head, not the other guys head.

Assume you are one of the blue.
n=1: You can easily tell that you must be it.

n=2: If you're not blue, the other guy should leave, if you're blue, the other guy should stay, so his actions determine your color.

n=3: regardless of what you assume about your own eye color, the other guys will not leave after day 1, so the fact that they don't leave tells you nothing, as you already knew they wouldn't leave (regardless of what your own eye color was). But... Forget perfect logicians for a moment. Suppose you had the following simple rule: If you see n people with blue eyes and they don't leave after day n, then leave on day n+1. If everyone followed this rule, they (the blue eyed people) would all get it right