The island where eye color can kill you.

February 15, 2008 7:47 AM

A mindbending logic puzzle. A thousand people on the island, 900 brown-eyed and 100 blue-eyed; anyone who learns their own eye color must kill themself the next day; a visitor mentions that there is a blue-eyed person on the island; what happens? Nothing, you say, because they already know that? Wrong. Further details at the Terry Tao post linked above, but don't scroll down below the boxed description unless you want hints and/or spoilers.

I'm not normally one for logic puzzles, but this one baffled and fascinated me to the point that I couldn't get my work done, so I thought I'd wreck your lives as well. If you want a complete spoiler, it's explained at the Wikipedia article on common knowledge. I note that some of the commenters at the Terry Tao post are remarkably stupid. (Via Avva; Terry's blog previously on MeFi in this post.)

posted by languagehat (384 comments total)

On 100th day, all blue eyed people kill themselves?
posted by trol at 7:55 AM on February 15, 2008

or possibly 101st, not thinking straight, its too early for me.
posted by trol at 7:55 AM on February 15, 2008

I have problems with a logic puzzle that consists of several illogical premises.
posted by Brandon Blatcher at 8:01 AM on February 15, 2008 [8 favorites]

I think I have this one solved. I should maybe Mefimail you.
posted by misha at 8:02 AM on February 15, 2008

I don't get how the islanders know that there are exactly 100 blue-eyed people on the island.

And 100 suicides? Can we submit this as evidence that religion is dangerous superstition and should be abolished?
posted by Mayor Curley at 8:03 AM on February 15, 2008

Argument 3: The tribesmen force the visitor to commit suicide in the town square because he knows the color of his own eyes. They then, of course, play soccer with his head.
posted by milarepa at 8:06 AM on February 15, 2008 [35 favorites]

Are they cannibals?
posted by Brandon Blatcher at 8:08 AM on February 15, 2008

milarepa wins.
posted by Faint of Butt at 8:08 AM on February 15, 2008

Among their many superstitions, notice that these people never look at reflections in water.

This is a fascinating study of an exotic culture. Thanks, Hat man!
posted by rokusan at 8:10 AM on February 15, 2008

The islanders do not know their own eye colors, but do they know that there are only two choices, i.e. blue and brown? Do they have any way of knowing, for example, that their own eyes are not green or hazel? Because then I can't answer the question.
posted by misha at 8:10 AM on February 15, 2008

Shame, too. The guy had an NSF grant and was about to make tenure.
posted by cog_nate at 8:11 AM on February 15, 2008 [3 favorites]

If brown and blue are the only choices, and are known to be so, I say they all die. Way to go, stupid visitor. Another culture wiped from the earth!
posted by misha at 8:11 AM on February 15, 2008 [2 favorites]

Why not just kill the foreigner? He admits knowing his own eye colour, and his painful death solves the problem.

On preview, milarepa beat me to it. That's what I get for editing.
posted by Chuckles McLaughy du Haha, the depressed clown at 8:12 AM on February 15, 2008 [1 favorite]

This should end soon.
posted by DU at 8:14 AM on February 15, 2008

I would wipe the whole place out by praising the beauty of the green eyes I saw on one of the tribesmen.
posted by JeremiahBritt at 8:15 AM on February 15, 2008 [11 favorites]

Also, why would 100% logical people kill themselves over eye-color. Alternatively, if eye color is really important for some reason, why would 100% logical people be bound by a taboo not to talk about it?

Also, why would such a rational group be unable to invent a mirror or even look in a pool of water?
posted by DU at 8:15 AM on February 15, 2008 [1 favorite]

This is a fascinating study of an exotic culture. Thanks, Hat man!

You're welcome! I visited the island myself, but of course having read the Lonely Planet guide I was sensitive enough not to mention eye color. No point reprinting the guide now, I guess...
posted by languagehat at 8:17 AM on February 15, 2008 [1 favorite]

Also, why would such a rational group be unable to invent a mirror or even look in a pool of water?

'Cause the island is in the middle of an ocean of lava. Lava!

Neat post, by the way.
posted by cog_nate at 8:18 AM on February 15, 2008

I thought I understood it until i read the answer and now I dont have a clue what its about. Not exactly flash friday fun is it
posted by criticalbill at 8:18 AM on February 15, 2008

I'd like to visit this island. Where is it?
posted by parki at 8:19 AM on February 15, 2008

It may make more sense to assume that the tribe only comprises vampires, whom we all know don't cast a reflection. Because that would make more sense.
posted by Admiral Haddock at 8:19 AM on February 15, 2008 [12 favorites]

I don't get how the islanders know that there are exactly 100 blue-eyed people on the island.

Well, assuming they're attentive, they certainly know that there are no more than 100 blue-eyed people on the island. The lower-bound question is trickier—the point about more than two potential eye colors is valid, I think, and isn't addressed in Tao's formulation.

The plane takes off.
posted by cortex at 8:20 AM on February 15, 2008 [1 favorite]

There's a fundamental problem with his logic. If I'm blue-eyed and don't know it but see a single other blue-eyed person, I'll just assume that that is who is being referred to. In addition, if that person does not commit suicide I'll think that they're not devout. If they do commit suicide there's no need for me to think about it anymore.

Or... what am I missing?
posted by dobbs at 8:20 AM on February 15, 2008 [2 favorites]

In the induction argument (all of the blue eyed people commit suicide on the 100th day), the day after all the blue-eyed people commit suicide, the rest of the inhabitants also commit suicide, as they now realize that they don't have blue eyes (and therefore have brown eyes).

However, highly logical people would recognize the implicit false dilemma between blue eyes and brown eyes and no one would kill themselves.
posted by graymouser at 8:21 AM on February 15, 2008 [1 favorite]

Having a lava ocean handy makes ritual suicide that much easier to execute. Just sayin'.
posted by cog_nate at 8:22 AM on February 15, 2008

I don't think that brown and blue are the only known choices, just the only two represented choices. Even if all the blue-eyed people commit suicide, any observer in the tribe will not know their own eye color, even if they know that everyone else has brown eyes.

I do, by the way, understand after thinking about it the solution in which all blue-eyed people commit suicide.
posted by OmieWise at 8:22 AM on February 15, 2008

Post-script: the blue-eyed people each know there's no more than 100 blue-eyes, and no less than 99. The brown-eyed people know there's no more than 101 blue-eyes, and no less than 100. Which is what, in theory, saves the brown-eyes from the mass suicide on Day 100.

And because the brown-eyes don't know that there's not, say, a green-eye among the surviving brown-eyes, no individual surviving brown-eye knows that he is a brown-eye. Ergo, he doesn't know his own eye color and doesn't kill himself.
posted by cortex at 8:23 AM on February 15, 2008 [1 favorite]

I'll think that they're not devout

I don't believe that's an option. It seems clear that they all default to devout and default to considering their neighbors devout.
posted by OmieWise at 8:24 AM on February 15, 2008

If I'm blue-eyed and don't know it but see a single other blue-eyed person, I'll just assume that that is who is being referred to

But there are 100 blue eyed people on the island and surely you've seen more than 1 blue eyed person.

If they do commit suicide there's no need for me to think about it anymore.

If it was your parents who committed suicide you might wonder if you're blue eyed.
posted by Brandon Blatcher at 8:24 AM on February 15, 2008

the blue-eyed people each know there's no more than 100 blue-eyes, and no less than 99.

How do they know this?
posted by Brandon Blatcher at 8:25 AM on February 15, 2008 [2 favorites]

But he does repeat himself, apparently, cortex. ; )
posted by misha at 8:26 AM on February 15, 2008

what happens if one of the blue-eyed people is blind? what happens then?
posted by criticalbill at 8:28 AM on February 15, 2008

How do they know this?

Presumably, they can count.
posted by dobbs at 8:31 AM on February 15, 2008

I have problems with a logic puzzle that consists of several illogical premises.

Yeah, I'll say.

The islanders do not know their own eye colors, but do they know that there are only two choices, i.e. blue and brown?
Well, in this case they see everyone else's eyes. They would know that 99 other people have blue eyes, but if they already knew that there were a total of 900 brown eyed people, and 100 blue eyed people, all one thousand would already have killed themselves. So, clearly no one in the tribe knows the exact number of blue or brown eyed people. They only know the number +/- 1.

Also, lets assume that the people on this island do follow the path of reasoning laid out and kill themselves. What prevents a brown eyed person from killing themselves? If 100 people do kill themselves, it seems like most of the people who die would be brown eyed. Except, seeing brown eyed people kill themselves would obviously illustrate the flaw in that particular train of thought.

So my answer is that nothing happens, and the argument that all the blue eyed people would kill themselves is nonsense. It's the same kind of "logic" that says an airplane won't take off if it's on a treadmill. It makes perfect sense to the to the thinker, but it is flawed at the foundation.
posted by delmoi at 8:33 AM on February 15, 2008 [1 favorite]

I think it helps to make the numbers smaller.

There are ten people on the island, one blue eyed, the rest brown. quonsar says it's nice to see another blue-eyed person. Bluey kills himself the next day because he can see nine brownies.

ten people, two blueys, eight brownies. quonsar stirs shit up. bluey1 thinks q could be talking about bluey2, so does not kill himself. bluey2 thinks the same thing, so does not kill himself. When neither kills himself the next day, they both know that the other bluey must be seeing another bluey, or they would have offed themselves!, which means that since they both see eight brownies (Ummm! Brownies!), they must be the other bluey. Both kill themselves on quonsay day+2. Etc. All the brownies are still alive because no one told the islanders there are only two eye colors.

I could be wrong.
posted by OmieWise at 8:34 AM on February 15, 2008 [16 favorites]

If we add to this wacky eye-color religion that the Holy Book informs them there are only two eye colors, then our hapless traveler wipes out the entire population on day 100, right? Am I getting this right?
posted by The Bellman at 8:34 AM on February 15, 2008

But there are 100 blue eyed people on the island and surely you've seen more than 1 blue eyed person.

No no no. If they knew that there were a total of 100 blue eyed people on the island, then everyone would already know their own eye color, and killed themselves when they noticed that there were a total of either 99 or 100 other blue eyed people.

So they can't know the total number of blue or brown eyed people.
posted by delmoi at 8:35 AM on February 15, 2008 [1 favorite]

So they can't know the total number of blue or brown eyed people.

No, they aren't TOLD there are 100 people with blue eyes and 1000 with brown, but they can see that there are 99 people with blue eyes and 1000 with brown or 100 blues and 999 browns if they have brown eyes. They just don't know they're the 100th blue eyed or the 1000th brown eyed.
posted by dobbs at 8:37 AM on February 15, 2008

How do they know this?

Assume (and given the premises we're dished, this isn't a far cry) that these villagers all know one another. So you have two cases:

1. Villager is brown-eyed. He looks at (or devoutly recalls) the eyes of his 999 friends and neighbors and knows that 100 of them have blue eyes and 899 have brown. His own eyes, he does not know; if he is brown-eyed, there are 100 blue-eyes. If he is blue-eyed, there are 101 blue-eyes.

2. Villager is blue-eyed. He knows that there are 900 brown-eyes and 99 blue-eyes, and him. If he is brown-eyed, there are 99 blue-eyes. If he is blue-eyed, there are 100 blue-eyes.

So browns know there are between 100 and 101 blue-eyeses; blues know there are between 99 and 100.

Following the stated induction solution, any given blue will know that there will be a mass suicide on the 99th day if he's not a blue-eye; and so on the 99th day he doesn't not commit suicide, as he still doesn't know his eye-color. Thereafter, when there is no suicide (because every blue-eye has to this point reasoned thus), he will know there are not 99 but 100 blue-eyes, and that he must therefore be a blue-eye. So he kills himself on day 100.

Each brown-eyes has been, by the same reasoning, sweating the hell out of day 100 and hoping (if hating himself for it) that all the blue-eyes he knows kill themselves that day, because he has reasoned that if day 100 isn't a mass suicide, there must be a 101st blue-eye. And that'd be him, and he'd be killing himself on day 101.
posted by cortex at 8:38 AM on February 15, 2008 [2 favorites]

ten people, two blueys, eight brownies. quonsar stirs shit up. bluey1 thinks q could be talking about bluey2, so does not kill himself. bluey2 thinks the same thing, so does not kill himself. When neither kills himself the next day, they both know that the other bluey must be seeing another bluey, or they would have offed themselves!, which means that since they both see eight brownies (Ummm! Brownies!), they must be the other bluey. Both kill themselves on quonsay day+2. Etc.

OmieWise has it. Excellent summary.

Also, why would 100% logical people kill themselves over eye-color. Alternatively, if eye color is really important for some reason, why would 100% logical people be bound by a taboo not to talk about it?

I take it you don't care for logic puzzles. That's fine, but complaining about things like that is like complaining that you can't smell the oceans on a map.
posted by languagehat at 8:39 AM on February 15, 2008 [20 favorites]

Assume (and given the premises we're dished, this isn't a far cry) that these villagers all know one another.

And they've all counted each other's eye color? That's a stretch.
posted by Brandon Blatcher at 8:42 AM on February 15, 2008 [1 favorite]

If we add to this wacky eye-color religion that the Holy Book informs them there are only two eye colors, then our hapless traveler wipes out the entire population on day 100, right? Am I getting this right?

Not quite; if "if not blue, then brown" was a given, the brown-eyes would kill themselves the NEXT day, having only discovered their brown-eyedness when the blue-eyes killed themselves on day 100.
posted by cortex at 8:42 AM on February 15, 2008 [2 favorites]

Well, no because we are assuming that all the blue-eyes figure it out at the same time and commit mass suicide, so why wouldn't the equally clever brown-eyes do so?
posted by The Bellman at 8:43 AM on February 15, 2008

And they've all counted each other's eye color? That's a stretch.

There's not much to do. They're highly numerate. The deathly prohibition against eye-color knowledge has turned them into obsessive eye-watchers.
posted by cortex at 8:43 AM on February 15, 2008

I approach this problem from a different angle. Suppose the visitor had said "I see 100 blue-eyed people." Obviously, all the brown-eyed people would already know that and sleep well, and all the blue-eyed people, knowing that they can only see 99 blue-eyed people, would figure out that they must have blue eyes and kill themselves that very night.

Now suppose that the visitor had said "I see at least 99 blue-eyed people." Everybody would sleep well the first night, because each of the blue-eyed people knows of exactly 99 blue-eyed people. The second night, though, each of those blue-eyed people would realize that nobody killed himself, and therefore there must be one more blue-eyed person than he can see, and that must be him. So on the second night all the blue-eyed people would kill themselves.

Obviously this can be extrapolated down to the visitor saying what he says in the puzzle. The blue-eyed people will always all kill themselves on the (101-N)th night, where N is the "at least" number of blue-eyed people the visitor says he can see. So, in the puzzle as given, the blue-eyed people will all kill themselves on the 100th night.

I find it much easier to understand the answer approaching it this way.
posted by cerebus19 at 8:44 AM on February 15, 2008 [8 favorites]

0.o
posted by ZachsMind at 8:45 AM on February 15, 2008

Well, no because we are assuming that all the blue-eyes figure it out at the same time and commit mass suicide, so why wouldn't the equally clever brown-eyes do so?

See above, on the collectively known lower- and upper-bounds. The brown-eyes don't have the same bounds as the blue-eyes; they wouldn't kill themselves (based on a mistaken presumption by each and every brown-eye of his own blue-eyedness) until day 101; they do not know they have brown eyes until the blue-eyes all kill themselves and reveal thereby that the brown-eyes are all, in fact, brown-eyes. And then it's a really dismal stretch until noon the next day before they off themselves.
posted by cortex at 8:45 AM on February 15, 2008

There's not much to do.

Nobody needs to catch food or build shelter, etc, etc :)

Anyway, laying out the culture of such a tribe sounds much more interesting than the puzzle.

Since it's taboo, it makes it sexy, so surely some of them are asking each other what they're eye color is. And there's always going to be some rebel who doesn't follow the custom. There might also be social customs where they dress or paint each other since they can't look in a mirror or the water.

Or maybe they all wear sunglasses.
posted by Brandon Blatcher at 8:49 AM on February 15, 2008

No-one has to know how many colours it's possible to have. I think OmieWise above has it -working up from 1 person in the group being blue and killing himself straight off, then thinking what the two people would do etc.
posted by Gratishades at 8:51 AM on February 15, 2008

And I'd suggest that none of the brownies would kill themselves the day after as each of them, for all they know, might be a special snowflake with different colour of eyes than everyone in their group.
posted by Gratishades at 8:55 AM on February 15, 2008

OK, cortex that makes no sense to me at all. I get the 100 days to blue-eye extinction thing: I'm a blue-eye; I've been waiting around, day after day; day 100 comes along and there has been no mass suicide so I think "well, it's day 100, I only count 99 blue-eyes, I must be number 100"; at that point I off myself and so does every other blue-eye who has been making the same calculation.

At that same instant every brown-eye (who knows he's either a blue-eye or a brown eye) has been making the same calculation, but waiting for day 101, because he or she sees 100 blue eyes. Now he sees the mass suicide and thinks, at first: "Whew! I guess I'm safe."

But then, he thinks: "Wait, all of those people were looking around and killed themselves on day 100 -- they must have only seen 99 blue-eyes. And since 100 blue-eyes just offed themselves, there must be only brown-eyes left. And that makes me a . . . . BRING ME MY SHARPENED CONCH SHELL!"
posted by The Bellman at 8:56 AM on February 15, 2008 [2 favorites]

Oh, I see what the argument is. Because no one leaves the island for 100 days, the islanders are able to determine the number of people with blue eyes. And once they learn that number, all the blue eyed people kill themselves. And then the next day all the brown eyed people would kill themselves as well.

On wikipedia, there is a slightly different formulation, where people 'leave' the island rather then being killed. Interestingly that makes it easier to understand the argument, because it's hard for people to imagine other people wanting to kill themselves.

The problem with the wikipedia explanation is that it only goes up to k=2, which is easy to understand.

First, imagine there is only one blue eyed person. When the traveler mentions that, the blue eyed person realizes they have blue eyes. Obvious.

Second, imagine there are two blue eyed people. When the traveler mentions that the blue eyed person sees the other blue eyed person not kill themselves the first day. So the second day, they realize that the two of them have blue eyes, and they both kill each other.

And that's as far as wikipedia takes it.

But what about the third case? If there are three blue eyed people, each of them will simply assume that the traveler was talking about one of those two people. And the argument would say that after the second day, when they don't kill each other they would all realize there were three blue eyed people, and that they were each one of them.

But in order for this to work out, you have to assume that everyone "starts counting" on that start date. What if on the third day one of those blue eyed people thinks that it's possible that one of those other blue eyed people didn't hear the news, or forgot, or something. In the problem explanation, it's given that everyone is hyper-rational and aware that everyone else is.

So, in this setup, the statement "one of you has blue eyes" is equivalent to the statement "Okay, everyone start counting days to determine who has blue eyes and who does not."
posted by delmoi at 8:59 AM on February 15, 2008 [1 favorite]

Gratishades: agreed, with the original problem statement by Tao. Blues kill themselves; Browns don't know they're all Browns, and don't.

The Bellman and I are arguing a variation where knowledge that everyone must either be blue-eyed or brown-eyed is somehow given. And thus:

At that same instant every brown-eye (who knows he's either a blue-eye or a brown eye) has been making the same calculation, but waiting for day 101, because he or she sees 100 blue eyes. Now he sees the mass suicide and thinks, at first: "Whew! I guess I'm safe."

I think the only thing we're disagreeing on is that "same instant" bit. I'm saying that they won't say, "whew, I'm safe." They'll know, as they see the Blues commit suicide, that they're none of them Blue, and hence by our variation they know themselves all to be Browns. But the instant of noon, by my reading, has passed; these are devout people of ritual and aren't about to engage in a late mass suicide at 12:01 or 12:03 or however long it takes them to get their conches together. And so they wait until the annointed time on the next day.

If they're more casual about the timeframe, then, sure: they get their sloppy seconds on as soon as they can cogitate on the Blue massacre.
posted by cortex at 9:02 AM on February 15, 2008

But the problem states that there are all different kinds of eye colors, it just so happens that this island only has blue and brown. So the only conclusion that the remaining 900 can make after the 100 blue-eyed islanders is kill themselves is not "there are 900 brown-eyers left" but instead "there are 900 non-blue-eyers left".
posted by turaho at 9:02 AM on February 15, 2008

cortex, The Bellman

I think your argument boils down to (or begs the question) "Once one person kills themselves, can someone else use that information to kill themselves now, or must they wait one day to process the information?" Or "how long is 'noon'"

Also (now that I realize it), it's possible that each brown eyed person might think they were the one hazel-eyed motherfucker on the beach, and not kill themselves.
posted by delmoi at 9:02 AM on February 15, 2008

What I don't understand is, wouldn't all the brown-eyed people all kill themselves at the same time as the blue-eyed people for the same exact reasoning that the blue-eyed people would?
posted by yeoz at 9:04 AM on February 15, 2008

Thanks for this. Friday logic fun!
posted by anotherpanacea at 9:04 AM on February 15, 2008

My response was to Bellman before I realized he and cortex were arguing a variation on the original problem. Oops.
posted by turaho at 9:07 AM on February 15, 2008

I see a marketing opportunity for coloured contact lenses.
posted by blue_beetle at 9:07 AM on February 15, 2008

Got it, cortex. You're right -- it's about the definition of "noon" which I had missed. They all glance down at their perfectly synchronized, non-reflective watches and, realizing it is no longer noon, go back to their ordinary lives for 23 hours and 59 minutes. Then, conch shells for everyone! Oh yes, there will be blood!
posted by The Bellman at 9:09 AM on February 15, 2008

Through the recessive genetics of the blue-eyed, some of the grandparents will eventually kill themselves. Though that would be outside the scope of this puzzle.
posted by Blazecock Pileon at 9:10 AM on February 15, 2008

Those tribesmen aren't logical at all. The logical thing would be to not think about eye colour and thus spare yourself the necessity of suicide. Giving the matter further consideration beyond "That guy's a douche!" is extremely illogical.
posted by Pope Guilty at 9:10 AM on February 15, 2008

I see a marketing opportunity for coloured contact lenses.
posted by blue_beetle at 12:07 PM on February 15 [+] [!]

I see a very short-lived and ill-conceived marketing opportunity for mirror shades.
posted by The Bellman at 9:11 AM on February 15, 2008 [3 favorites]

What I don't understand is, wouldn't all the brown-eyed people all kill themselves at the same time as the blue-eyed people for the same exact reasoning that the blue-eyed people would?

No, because their assessment of how many blue eyed people there are is always one higher than that of blue-eyed people.
posted by Pope Guilty at 9:13 AM on February 15, 2008

And while we're arguing premise-breaking variations, I think a little bit of colorblindness in the mix would be hilarious.
posted by cortex at 9:13 AM on February 15, 2008

((Pope Guilty just made me lose the Game. Damn you, PG, I was on a roll!))
posted by The Bellman at 9:15 AM on February 15, 2008

I believe that there is a user named "You just lost the game."
posted by Pope Guilty at 9:19 AM on February 15, 2008

Thanks cortex for taking the time to explain that.
posted by saladin at 9:19 AM on February 15, 2008

I think I got it l-hat! Nice puzzle!
posted by vronsky at 9:22 AM on February 15, 2008

I believe that there is a user named "You just lost the game."

Aye, there is.
posted by cortex at 9:24 AM on February 15, 2008

i think in OmniWise's version Bluey1 thinks it is possible that he himself is a green eye or red eye or whatever and he is okay with the fact that Bluey2 didn't kill himself because Bluey1 assumes Bluey2 has no idea that he (Bluey2) is a blue-eye.

If there is the possibility of more than 2 colors then any one villager could assume they are the 1 person of that non-blue or non-brown eye color.

If there is the dictum that "All villagers know that there is only brown and blue" then I believe the outcome is that they will all kill themselves according to the common knowledge logic.
posted by rlef98 at 9:30 AM on February 15, 2008 [1 favorite]

I don't think the induction is valid. In the inductive step, the islanders are assuming the truth of the theorem, which means they must have proved it somehow. And "our" proof depends on them actually committing suicide, which they only do if they've proved it. But our proof can't depend on itself; therefore it's only valid if there's another proof. So our proof is useless. The theorem may be true, but this isn't a proof of it.

But I don't see how the theorem can be true. The traveler's statement is redundant; everyone already knows that there's at least one blue-eyed islander. If they were going to kill themselves, they'd still do it without the traveler.
posted by equalpants at 9:33 AM on February 15, 2008 [1 favorite]

I'm unclear why the correct answer is "the entire island converts to Christianity."
posted by dw at 9:36 AM on February 15, 2008 [1 favorite]

Once upon a time, on an island far, far away, there was a native named Idiot Jed. Idiot Jed had bulging muscles, greasy hair, shining blue eyes, and was (secretly) not obsessed with logic puzzles. When anyone brought up a logic puzzle (which was all the damn time), Idiot Jed would shout "Kirsten sits next to Lord Bickerstaff who does not own a pony!" and run off to rotate the coconuts.

One day, a stranger showed up on the island, and said some crap about blue eyes. "He's talking about my friend Doug", thought Idiot Jed. "Doug has blue eyes. Doug is my friend." For the next few days, everyone on the island ran around looking worried and keeping logs of eye colors, while Idiot Jed worked on his car stereo. Then on day 100, the other 99 blue-eyed people on the island killed themselves. On day 101, most of the brown-eyed people's heads exploded, and the rest began randomly stabbing each other while sobbing "Does not compute". Eventually, Idiot Jed took control of the demoralized survivors and started a new religion based on driving cars very fast.

And today, we call that island... North Carolina!
posted by ormondsacker at 9:37 AM on February 15, 2008 [2 favorites]

I have problems with a logic puzzle that consists of several illogical premises.

damn right.

the problem i'm having is that the islanders are all highly "Logical" AND highly "Devout." Those two just don't mesh well.

Logical implies reasoning. It would mean that each and every islander would have attempted to reason out exactly who had blue eyes or brown eyes long ago, before the foreigner ever even arrived. They'd have counted. They'd have figured it out.

But they're also Devout. And they're religion seems to practice from a point of Ignorance, being that they should NOT attempt to discover anything about eye color.

So either they're instincts are to discover their eye colors or to ignore them. Not both. I realize this is a hypothetical, but its a poorly drawn one. It would have been better expressed only mathematically. I have a problem when logic problems get expressed as word problems improperly and cause the premises to not make sense any longer. I could conclude anything I wanted, really.

So sure, after 100 days the islanders have a big orgy, drink some Evan Williams, crown the foreigner king, and fuck off to Narnia.
posted by mr_book at 9:38 AM on February 15, 2008

why the correct answer ISN'T.

Blew the joke. DAMN YOU MATHOWIE FOR NOT LETTING US EDIT OUR COMMENTS!!!!! I WILL GET YOU YOU BROWN EYED BASTARD!
posted by dw at 9:38 AM on February 15, 2008 [1 favorite]

I got the answer and accept the conclusion, but then I started thinking: "wait, say I'm a villager and heard the pronouncement. What did I just learn?" I don't get the appeal to common knowledge. I knew there was a blue-eye, and knew that everyone else knew that. So what's the piece of common knowledge that the community gained?

Then I loaded up the wikipedia page languagehat linked to and saw that there was a formalization of common knowledge in modal logic. This is great. I'm going to puzzle over it for a while.
posted by painquale at 9:38 AM on February 15, 2008

the problem i'm having is that the islanders are all highly "Logical" AND highly "Devout." Those two just don't mesh well.

You must be a hoot at parties.
posted by dw at 9:39 AM on February 15, 2008 [1 favorite]

cortex: The plane takes off.

Indeed. Previously discussed in the conveyor belt thread. [**CONTAINS SPOILERS**]
posted by goodnewsfortheinsane at 9:40 AM on February 15, 2008

I would have to agree with the poster at the site who said: "There’s no new information here. The foreigner merely acknowledges that there are people of blue eye colour on the island, and this is a fact previously established by the islanders through observation."

Given this and the induction, the blue eyed people would already have killed themselves, which means the puzzle could not exist - even as a hypothetical.
posted by dances_with_sneetches at 9:40 AM on February 15, 2008 [1 favorite]

equalpants: The traveler's statement is redundant; everyone already knows that there's at least one blue-eyed islander. If they were going to kill themselves, they'd still do it without the traveler.

From the wikipedia page: "What's most interesting about this scenario is that, for k > 1, the outsider is only telling the island citizens what they already know: that there are blue-eyed people among them. However, before this fact is announced, the fact is not common knowledge."
posted by painquale at 9:40 AM on February 15, 2008

This isn't mindbending, it's consfusing.
posted by Stonestock Relentless at 9:42 AM on February 15, 2008 [1 favorite]

OmieWise writes...
ten people, two blueys, eight brownies. quonsar stirs shit up. bluey1 thinks q could be talking about bluey2, so does not kill himself. bluey2 thinks the same thing, so does not kill himself. When neither kills himself the next day, they both know that the other bluey must be seeing another bluey, or they would have offed themselves!, which means that since they both see eight brownies (Ummm! Brownies!), they must be the other bluey. Both kill themselves on quonsay day+2.

Excellent summary of the two blue situation, but then you wrote...

Etc.

Which is the same mistake that Terry Tao makes when he tries to use induction.

So -- ten people, four blueys, six brownies. quonsar stirs shit up.

Day one rolls around and everyone on the island can see at least see at LEAST three blueys. Let's call them A, B, and C. Any given observer will reach the following conclusions:

A can see both B and C so he has no reason to suspect that he's a bluey
B can see both A and C so he has no reason to suspect that he's a bluey
C can see both A and B so he has no reason to suspect that he's a bluey

Because of this mutual deadlock nobody is expected to commit suicide and nobody does.

Day two rolls around and the same deadlock exists.
Day three ....
Day four ...
Day five ...
Etc.

In short, when you have at least four blueys, you immediately reach the point where no one is committing suicide and *everybody knows why that is*. And it doesn't matter how many days pass.
posted by tkolar at 9:46 AM on February 15, 2008 [8 favorites]

On day 101, wouldn't all the brown eyes people then know they had brown eyes, and be forced, by their weird tribal beliefs, to commit mass suicide.

There's my solution: everyone's dead. Everyone. Even you, you brown eyed freak.
posted by Astro Zombie at 9:48 AM on February 15, 2008

It's counter-intuitive, but I do understand the logic behind the second argument. In reality, however, most humans have trouble dealing with numbers higher than 5, or 10, making the first argument much more practical, if logically incorrect.

The second argument assumes that every islander knows exactly how many *other* blue-eyed and brown-eyed people are on the island--100 blue and and 899 brown or 99 blue and 900 brown, correct? It also assumes that the tribal members have an interest in determining *exactly* how many members have blue eyes and are willing to *sustain* that interest for nearly four moons.

Many primitive/ancient civilizations had words for 1, 2, and then "many" (ref) - I don't think it's in the realm of formal logic (of which I know very little) to account for cultural issues like that, but in all honesty, the first conclusion (though not logical) makes much more sense in reality. (Move the number down to a graspable set, like 5 or 10, and the second argument becomes more probable.)

My guess is self-preservation issues would cause 99.99% of humans to ignore the formal logic, put their fingers in their ears, and say "LA LA LA LA!!! I don't know exactly how many other blue-eyed tribe members there are!"

After a week, even the taste of that blue-eyed stranger's flesh would be forgotten. ;)

there are two separate and seemingly valid arguments which start with the same hypotheses but yield contradictory conclusions

Welcome to the universe.
posted by mrgrimm at 9:52 AM on February 15, 2008

Also, why would 100% logical people kill themselves over eye-color. Alternatively, if eye color is really important for some reason, why would 100% logical people be bound by a taboo not to talk about it?

Please produce the chain of logic that refutes either of these notions.

I know that the common meaning of the word "logical" is "makes sense (to me)" and I know that the Mr. Spock use of the word "logical" is too inconsistent to define, but here it just means that the islanders always reason clearly from premises to conclusions.

To put it in logical terms, the puzzle says the islanders always believe something if it can be logically deduced. It does not say that the islanders always believe something if and only if it can be logically deduced.
posted by straight at 9:55 AM on February 15, 2008 [3 favorites]

I can question the unstated-but-generally-agreed-upon conventions of a logic puzzle! I am so smart! S-M-R-T smart!
posted by DevilsAdvocate at 9:56 AM on February 15, 2008 [1 favorite]

Cortex's reasoning above lays out the logic of it exactly.

They can't kill themselves without the traveller to start their simultaneous induction process. Imagine being a blue eyed person on the island. You spend each and every day wondering if there are 99 or 100 blue eyed people. You never get a date to refer back to 99 or 100 days ago, when everyone could synchronise their logical processes. You have to wonder though how the islanders ever got through their first 99 or 100 days on the island without dying.
posted by roofus at 10:00 AM on February 15, 2008

I see a lot of people tearing out their own eyes on day 99....
posted by illuminatus at 10:03 AM on February 15, 2008

There's also the pirate puzzle:

There are five rational pirates, A, B, C, D and E. They find 100 gold coins. They must decide how to distribute them.

The Pirates have a strict order of seniority: A is superior to B, who is superior to C, who is superior to D, who is superior to E.

The Pirate world's rules of distribution are thus: that the most senior pirate should propose a distribution of coins. The pirates should then vote on whether to accept this distribution; the proposer is able to vote, and has the casting vote in the event of a tie. If the proposed allocation is approved by vote, it happens. If not, the proposer is thrown overboard on the pirate ship and dies, and the next most senior pirate makes a new proposal to begin the system again.

Pirates base their decisions on three factors. First of all, each pirate wants to survive. Secondly, each pirate wants to maximize the amount of gold coins they receive. Thirdly, each pirate would prefer to throw another overboard, if all other results would otherwise be equal.
posted by tksh at 10:13 AM on February 15, 2008

Yes, yes... but I have green eyes.
posted by markkraft at 10:20 AM on February 15, 2008

Really, though... Unless one of the villagers told me that I had blue eyes, then how would I know I *didn't* have green eyes? I would only know that 99 of you had blue eyes, and that 900 of you had brown eyes.

Maybe I'm a special little flower.
posted by markkraft at 10:24 AM on February 15, 2008

Just think if the traveler lied and said "Wow, only one green-eyed tribesman amongst ya. Think of the odds!"

Everyone would be dead the next day, having erroneously assumed they were the one.
posted by klangklangston at 10:25 AM on February 15, 2008 [1 favorite]

I could look at the villagers around me and think it's more statistically likely that I would be either brown or blue-eyed, but probability is not proof, and, therefore, not something I would act upon.
posted by markkraft at 10:28 AM on February 15, 2008

Everyone can see at least 99 blue-eyed people.

So everyone knows that there is a blue-eyed person on the island.

And because everyone can see more than one blue-eyed person, everyone also knows that everyone else on the island knows that there is a blue-eyed person on the island.

So, when the traveller arrives and tells everyone there is a blue-eyed person on the island...

He provides no new information.

To anyone.

He cannot affect anything.

The premise of the puzzle is flawed, because under the puzzle's own logic, the stable situation described could not have come about. The people of the island would have already committed suicide, or if they had not, they would be due to soon, and the traveller's appearance would not speed their departure.
posted by East Manitoba Regional Junior Kabaddi Champion '94 at 10:32 AM on February 15, 2008 [2 favorites]

Damn your logic you green blooded pointy eared blue eyed hobgoblins!
posted by tkchrist at 10:35 AM on February 15, 2008

tkolar: John Armstrong's comment from the Terry Tao thread may help:

n=2. Each blue-eyed person says: “If I am not blue-eyed, then there is one blue-eyed person on the island, and he will kill himself tomorrow because of what the traveller just told us.”

“But then the next day comes and the other doesn’t kill himself! That must mean there are two blue-eyed people, and I am the other one!”

n=3. Each blue-eyed person says: “If I am not blue-eyed, then there are two blue-eyed people on the island. They are each looking at each other and thinking (”If I am not blue-eyed, then there is one blue-eyed person on the island, and he will kill himself tomorrow because of what the traveller just told us.”). But neither will kill himself tomorrow, and they will realize their mistake tomorrow and kill themselves on the day after.”

“But then the third day comes and they don’t kill themselves! That must mean there are three blue-eyed people, and I am the third!”
posted by languagehat at 10:35 AM on February 15, 2008 [3 favorites]

Yep, that's why it has to be n=4 for the deadlock to be reached immediately. If no one is expecting anyone to kill themselves tomorrow, no new information is gained when nobody does.
posted by tkolar at 10:40 AM on February 15, 2008

I'm approaching this puzzle on a completely different level:

Heh-Heh, you said "brown-eyes".
posted by Horace Rumpole at 10:40 AM on February 15, 2008

Or, I should say, n >= 4.
posted by tkolar at 10:41 AM on February 15, 2008

But, tkolar, why do you think that for n=4 the rules change. The day of suicide is equal to n, so for larger values of n the day of reckoning just comes later.
posted by OmieWise at 10:43 AM on February 15, 2008

*gouges out eyes*
posted by chugg at 10:45 AM on February 15, 2008

Ok, for all those who are having trouble with the people being logical and devout, think of them as robots with or without spots on their heads. They have the the instruction set that they move themselves into a corner if they have a spot on their head, they have working visual sensors and also start with the knowledge that there is at least one robot with a spot on its head in the room.

Same problem, leaves out the human factor.
posted by Hactar at 10:49 AM on February 15, 2008

An interesting twist exists for the special case where the islanders know that the only two eye colors are brown and blue. If the rules of their religion were they were never allowed to know the color of their eyes, they'd kill themselves on day 1, since once the tourist mentioned seeing a single eye color, they were all doomed to know their eye color. In other words, they might not know at that moment in time what their eye color was, but they knew that it was only a matter of time, and being such devout islanders would kill themselves for that very reason.

Of course, if the suicidal edict is interpreted to only be in force when they absolutely know the color of their eyes, then the blues would kill themselves on day 100, and the browns on day 101 as mentioned above.
posted by forforf at 10:50 AM on February 15, 2008 [1 favorite]

Of the 1000 islanders, it turns out that 100 of them have blue eyes and 900 of them have brown eyes, although the islanders are not initially aware of these statistics

And they still are unaware as the foreigner did not tell them of these statistics, he only says that ONE of them is blue eyed, which they already know.
posted by Pollomacho at 10:50 AM on February 15, 2008

I'm sorry, all this discussion is reminding me of Vizzini debating Westley while trying to decide which cup holds the poison.
posted by etaoin at 10:52 AM on February 15, 2008 [3 favorites]

This island's religion makes cargo cults look positively not goofy. Although, I guess their rules are no less arbitrary than "God hates shrimp".
posted by DecemberBoy at 10:54 AM on February 15, 2008

Okay, I think I see what's going on. Here's the inductive step, as given by Tao and by the Wiki page:

Inductive step: if n-1 blues commit suicide after n-1 days, then n blues commit suicide after n days.
Proof:
1. Assume inductive hypothesis: n-1 blues die after n-1 days.
*2. Consider an island with n blues, in a world in which it is true that n-1 blues die after n-1 days.
3. Each blue on this island sees n-1 blues; knows that there are either n-1 or n blues overall.
*4. Each blue knows that n-1 blues will die after n-1 days.
5. Each blue sees n-1 days go by without death, concludes that there are n blues.
6. Each blue now knows his own color; dies the next day.

The trick is in steps 2/4. We're giving the islanders in our hypothetical world access to our inductive hypothesis. We're saying, "Consider a world in which fact X is true; the islanders in this world know that X is true, since they know everything." We're not specifying how the islanders know X. Can they possibly have a proof of X? Yes, but not this proof, because that would be an infinite regression.

The key is in the statement of the problem, where we assume that the islanders know the truth of everything, even things which can't be proved. We don't provide the proof that the islanders are using; instead we assume that they don't need one, so it doesn't matter whether or not they have one.

So I think the wording of the problem is the source of the confusion. This is really a knights-and-knaves-type problem, where the inhabitants are oracles, but Tao just says that they're "highly logical". Is it reasonable to infer "oracle" from "highly logical"? Well, that's a philosophical question.
posted by equalpants at 10:54 AM on February 15, 2008

But, tkolar, why do you think that for n=4 the rules change. The day of suicide is equal to n, so for larger values of n the day of reckoning just comes later.

The induction argument is intimately tied to the idea that you as an islander are expecting someone else to commit suicide, and that you make a new deduction when you see that they don't.

If you you have no expectation of anyone committing suicide (as I layed out above for n=4) the inductive argument falls apart.
posted by tkolar at 10:55 AM on February 15, 2008

But I don't think you do away with the expectation, that's what I'm asking you about. I think you're ignoring the constants, which are the day of the revelation and the number of people on the island.

The day of reckoning is visible blueys + 1.

The expectation is that no matter how many visible blueys there are, if they don't commit suicide on day=visible blueys, then you know there's one more bluey than there are visible blueys.

Since i islanders=(visible brownies+visible blueys-you), the only other possible bluey is you.
posted by OmieWise at 11:01 AM on February 15, 2008

after going through this problem several times i have come to the inescapable and inevitable conclusion that this island must have been located in the middle east
posted by pyramid termite at 11:02 AM on February 15, 2008

Paging asavage...
posted by thirteenkiller at 11:04 AM on February 15, 2008

If Omie's explanation still doesn't work for you, here's another one.'

Somewhere in my investigation of this problem—alas, I don't remember where—I ran across a comment to the effect that a farsighted islander could short-circuit the whole thing by killing a blue-eyed islander immediately after the announcement, preventing further violence.
posted by languagehat at 11:06 AM on February 15, 2008

1. This assumes that no one kills themselves for any other reason.
2. It also assumes that people would deliberately seek out knowledge that might end up with them having to kill themselves. Which is silly because they would avoid this just like mirrors. I don't know many people's eye colors and knowing it doesn't kill me. I think islanders would avoid inventoring other people's eye colors just as they would avoid looking into a pool of standing water.
posted by I Foody at 11:06 AM on February 15, 2008

For n = 4, each person knows that there are 3 other persons with blue eyes.

The foreigner makes his comment but doesn't specify the person or an upper-bound.

So each could simply think none of the other three would be sure of their own status (analogous to our subject) and hence, no suicide expected, and no suicides.
posted by Gyan at 11:11 AM on February 15, 2008

The expectation is that no matter how many visible blueys there are, if they don't commit suicide on day=visible blueys, then you know there's one more bluey than there are visible blueys.

On the contrary -- if the blueys that you can see (and it only takes three) are in a logical deadlock where none of them have any reason to suspect a problem, then you have no reason to suspect anything at all about yourself. You know that there are at least three blue eyed people on the island and you know why they're not killing themselves.
posted by tkolar at 11:11 AM on February 15, 2008

"And they still are unaware as the foreigner did not tell them of these statistics, he only says that ONE of them is blue eyed, which they already know."

But no one has discussed it. That's the new information.
posted by klangklangston at 11:15 AM on February 15, 2008

Gyan wrote...
For n = 4, each person knows that there are 3 other persons with blue eyes.

The foreigner makes his comment but doesn't specify the person or an upper-bound.

So each could simply think none of the other three would be sure of their own status (analogous to our subject) and hence, no suicide expected, and no suicides.

Exactly so.
posted by tkolar at 11:15 AM on February 15, 2008

Man, it is really hard to see what new information the visitor brings. He has to bring something new, otherwise everyone would have killed themselves long ago, as many people in this thread have pointed out.

But it can't be the case that he brings no new info, because everyone accepts (or should accept, anyway) the following argument: if there are only two blue eyed people on the island, then they'll both kill themselves after one day.

Consider the case where n=1 (that is, there's one blue-eyed villager). When the visitor makes his statement, the blue-eyed guy gains knowledge of proposition p: "someone has blue eyes". He kills himself the next day.

Now consider where n=2. What the each blue eyed person learns from the visitor's statement is not p, because everyone knows that someone has blue eyes (everyone can see a blue-eyed person). What they learn from the visitor's statement is proposition p2: "everyone knows that p". So after day 1 rolls around, the blue-eyed villagers can deduce from the lack of deaths and from p2 that they are blue eyed.

Now consider n=3. After 2 days, no one has killed themselves, but they kill themselves the next day because they learned from the visitor's statement p3: "everyone knows p2".

So, it looks like in order for the argument to go through, the visitor had to bring not just the information that someone has blue eyes (everyone in cases of n > 1 knew that already), but that everyone knows that someone has blue eyes, and that everyone knows that everyone knows that someone has blue eyes, and so on. However, to make it such that the visitor really did offer new knowledge, and the villagers wouldn't have all killed themselves beforehand, they couldn't have known this prior to the visitor's speech.

That's what is surprising to me. Intuitively, I would think that if I can see 99 other blue eyed people who can see each other, then I know that any other person knows that someone is blue eyed, and they know that I know that, and I know that they know that, etc. But this has to be denied for the visitor to actually bring new information. And that's weird. It's obvious how it all works out when n=2, but make the number of blue-eyeds any larger and it seems like I shouldn't deny it.

So I'm a little stymied. How is it that they didn't have this sort of recursive meta-knowledge beforehand? And what is it about the visitor's statement such that they gain this recursive meta-knowledge?
posted by painquale at 11:17 AM on February 15, 2008 [3 favorites]

I understand that you think that, I don't understand why you think there is a logical deadlock. I didn't understand your explanation of that deadlock.

If x blueys don't kill themselves on day n-1 then they didn't do it because they see n-1 blueys. They can only not kill themselves because they are at a day equal to or less than n-1. Once day=n, and no one dies, any observer o knows that it means that the number of blueys is not n-1 (the number he can see), but n, which means he's a bluey.

Why do you think this changes as n grows larger?
posted by OmieWise at 11:17 AM on February 15, 2008

More explicit version:

Theorem: In any world where the islanders are oracles (they know whether or not any statement is true), n blues die after n days.

Base case: Only one blue; easy proof. The proof of this case does not require the islanders to be oracles; this case would be true even in the real world.

Inductive step: Assume that, in any world where islanders are oracles, it is true that n-1 blues die after n-1 days. In any such world, n blues will die in n days, because the blues know that the n-1 case is true, discover their own color, etc.
posted by equalpants at 11:18 AM on February 15, 2008

I think there's something very intuitively appealing about tkolar's argument. Omiewise, if you start with his perspective -- what precisely do you see that's wrong with it?

In addition, I think the puzzle assumes without stating it that there is a particular time point (e.g. midnight each night) by which the villagers have made a discrete decision to kill themselves or not and can evaluate whether the others know something by whether they've acted or not.

Without that assumption, it seems like the villagers could as easily deduce from the others' lack of suicide that they simply had not yet decided to act rather than that they had decided NOT to act. As a result, the decision not to commit suicide could happen for the wrong reasons. This pollutes the information stream and screws up everyone's decisionmaking.

Or that's my sense, anyway.
posted by shivohum at 11:18 AM on February 15, 2008

Some of you people are reeeeeeeeeeally hung up on trying to inject human psychology into a puzzle that is pure logic. I understand why you would do this, since the agents in question are people and not widgets, but you have to understand it's the pure formal logic of this that's under analysis. Earth-shattering pronouncements like "you can't be both highly logical and highly religious to the point of suicide over eye color" are perfectly true and yet could not be further from the point of this exercise. See languagehat's comment above, if you missed it the first time around.

Pretend they're not humans. Pretend they're aluminum balls colored a certain color, and they have a chip inside them that both (a) allows them the power of logic for solving puzzles, and (b) requires them to roll off of a high cliff if they ever figure out what color they are.
posted by middleclasstool at 11:18 AM on February 15, 2008

That was to tkolar.
posted by OmieWise at 11:20 AM on February 15, 2008

The foreigner doesn't specify the upper bound, but the islanders themselves do. Look, I'm one of the islanders. I see 99 blueys and 900 brownies. I know for a fact that there are either 99 or 100 blue-eyes. It's one of the two. There are no more or less than either 99 or 100, because my own eyes tell me this.

If there's 99, they'll figure it out by the 98th day and kill themselves on day 99, following the inductive logic. If they don't do that, that means they're seeing exactly the same number of blue eyes I do, and we all go bang-bang on day 100.
posted by middleclasstool at 11:25 AM on February 15, 2008

If eye color was such a taboo, wouldn't they avoid looking at each other's eyes?

The last person can't kill himself, because they're supposed to commit a ritual suicide "for all to witness."
posted by kirkaracha at 11:25 AM on February 15, 2008

So each could simply think none of the other three would be sure of their own status (analogous to our subject) and hence, no suicide expected, and no suicides.

Except let's say there are four blue eyed islanders A, B, C, and D. Islander A knows there at at least 3 blueys. Now let A assume he's brown eyed. In that case, B would see two blueys. But then when islander B sees C and D not kill themselves on day two, B would know that he is blue eyed and kill himself on day three. When this doesn't happen, A concludes that his assumption that he is brown eyed must be false and must off himself right away.
posted by Schismatic at 11:26 AM on February 15, 2008

Come to think of it, even with n=3, there ought to be no suicides.

You have A, B, C as blue-eyes.

A doesn't commit suicide as he sees B & C with blue-eyes.
A expects that B expects C to commit suicide (A knows that B can see C).
A expects that C expects B to commit suicide (A knows that C can see B)

A hence realizes that neither will do so, and not because A himself is blue-eyed.

Similar for B & C.

The key is that the foreigner's remarks don't specify the person nor an exact number.
posted by Gyan at 11:30 AM on February 15, 2008

And the new information that the foreigner adds is more subtle than the existence of a single blued eyed person. Everyone knows that there is are at least 99 blue eyed folks, but what the statement does is inform the islanders that if one were to look around and see no pairs of blue eyes, he must kill himself. This is new information that affects how they interpret the behavior of the other islanders.
posted by Schismatic at 11:38 AM on February 15, 2008 [1 favorite]

EVERYONE would kill themselves on the 100th day.

EVERYONE would see on the 99th day that no one killed themselves.

EVERYONE, since they don’t know the color of their own eyes, would assume that *they* were the 100th.

And EVERYONE would die on the 100th day.

If you’re making the assumptions that lead to the second conclusion, then the real answer is the whole tribe is dead, on day 100.
posted by MythMaker at 11:38 AM on February 15, 2008

Gyan: But there are multiple days on which they can commit suicide. You can't just say that someone 'commits suicide' without specifying when.

He provides no new information.

Not for the n=100 case, but without the outsider, the base case for the induction (n=1) does not hold. If there were exactly one blue-eyed person on the island, he/she would not know for certain that there were any.
posted by obvious at 11:40 AM on February 15, 2008

More like this:

A doesn't commit suicide right away because he sees B&C.
A expects that no one will commit suicide tomorrow, because they can each see at least one guy with blue eyes. A knows he sees two, and he knows that B&C each see either one or two.
If B&C each see one, then they will kill themselves on the second day afterward, following the logic.
If B&C see two, then they won't, meaning the only possible remaining blue eye is A.

Similar for B&C.

Again, the remarks don't specify the exact number, but their eyes confirm only two possible numbers, n-1 or n. If it's n-1, they'll figure it out on day n-2 and kill themselves on day n-1. If not, then the nth person knows he's blue-eyed and must kill himself on day n.
posted by middleclasstool at 11:41 AM on February 15, 2008

MythMaker: No, because on the 100th day everyone but the blue-eyed person would notice that there was still one blue-eyed person left.
posted by obvious at 11:42 AM on February 15, 2008

Another inherent premise: the islanders overthink everything, almost with the aim of killing themselves.
posted by supercres at 11:47 AM on February 15, 2008

Can someone help me out with the common knowledge effect here?

I can understand how it works in the k=2 case. Before the visitor arrives, each of the two blue-eyed people know that there is at least one blue-eyed person, but they don't know that the one blue-eyed person they can see knows that there are any blue-eyed people. So each blue-eyed person thinks, "I see that guy has blue eyes. That means there are either one or two people on this island with blue eyes. Since he hasn't killed himself, it is possible that my eyes are brown and that (1) he doesn't realize there are any blue-eyed people on this island. Alternately, (2) my eyes are blue, but using the reasoning of proposition (1), he believes his eyes might be brown. Either way, I cannot deduce my eye color from his behavior." Upon the arrival of the visitor, everyone knows that there is at least one blue eyed person, so proposition (1) fails, and the countdown begins.

How does it work for k>2, though?
posted by mr_roboto at 11:49 AM on February 15, 2008 [3 favorites]

It works for k>2 because the third man realizes there are two cases, k=2 or k=3. If k=2, then it goes down as you describe, both the first two men kill themselves two days after the speech, so the third man knows he doesn't have blue eyes. If they don't kill themselves, then the only other possibility is that the first two men see a third blue-eyed man. Since the third man cannot see another blue-eyed man, then he must logically be it, so all kill themselves on day 3. Same for 4 and on up, following this same chain.
posted by middleclasstool at 11:53 AM on February 15, 2008 [3 favorites]

If the suicide thing is really bothering you (which it shouldn't, because this is a logic puzzle, not an anthropological study), then you could say instead that if someone learns the color of their own eyes, then the next day they must announce this fact to the whole island. As far as I can tell, the problem would be the same.
posted by obvious at 11:55 AM on February 15, 2008

OK, hang on one more time. If they have perfect logic, wouldn't they have already killed themselves?

I'm still not understanding why the traveler saying there's a person with blue eyes creates a problem. No, they don't know the stats, but observation would tell all these people that:

-- there are brown eyed people
-- there are blue eyed people
-- the observer has eyes and they're probably a color

It's that last thing that's throwing me. The traveler points out that he sees one blue-eyed person. He never says who it is. And he doesn't point out there are ONLY TWO OPTIONS.

So, a logical person, knowing that he/she sees a blue eyed person, can see that he might have been referring to that person. BUT THE OBSERVER STILL DOESN'T KNOW WHAT COLOR HIS/HER EYES ARE, BECAUSE HE/SHE DOESN'T KNOW ALL THE OPTIONS.

I mean, how do they know there are only brown and blue? It's likely, but that doesn't mean it's 100% true. And highly logical people aren't going to kill themselves without 100% certainty.

Seems to me the only logical solutions to this are to either commit mass suicide (because if one person has blue eyes, then everyone has blue eyes, even if they don't) or to kill the traveler (for offending their religion, and anyway, blue eyes he said so himself).

But this seems to fall apart in assuming there are only 2 choices in eye color. And in reality, there are N choices. And at no point are these highly logical people let in on what N is.
posted by dw at 11:56 AM on February 15, 2008

mr_roboto: See here. And to restate for anyone who hasn't gotten it: the new information that the foreigner brings is not that there are blue-eyed islanders, which they knew, but that the existence of such is common knowledge. Read the Wikipedia article and think about it again.
posted by languagehat at 11:57 AM on February 15, 2008

But how is the system stable prior to the arrival of the visitor for k>2? If the third man sees two blue-eyed people at any point in the history of the island, must he not assume that each of those people can see at least one other blue-eyed person? Doesn't the killing start at the moment of this realization, which does not depend on the arrival of the visitor?
posted by mr_roboto at 11:57 AM on February 15, 2008 [1 favorite]

Oops, I mean see here. Or just read middleclasstool's comment.
posted by languagehat at 11:58 AM on February 15, 2008

Hey languagehat, I've been struggling over the Wikipedia article, and hoping that someone could explain k>2 for dummies...
posted by mr_roboto at 11:58 AM on February 15, 2008

Some of you people are reeeeeeeeeeally hung up on trying to inject human psychology into a puzzle that is pure logic

Then stop using humans in pure logic puzzles :)
posted by Brandon Blatcher at 11:58 AM on February 15, 2008

dw: Everyone's eyes are either blue or non-blue, so in that sense there are only 2 choices.
posted by obvious at 12:02 PM on February 15, 2008

Paradoxes like this fascinate me for a couple of reasons: there's the paradox/problem itself, but there's the varied reactions to it. I've noticed that while one camp gets really into it, another is scornful.

When I was in my 20s, I became really fascinated with a story-problem puzzle. I told it to everyone I knew (I can't imagine do that now), and one of my friends surprised me by getting really irritated.

Me: I read this really great paradox. It goes like this: there's an island inhabited with two kinds of people, one that always lies and another that always tells the truth. A visitor walks up to an islander and says.... [I explained the rest of the problem.]

Friend: That's silly. No one is completely truthful all the time.

Me: No... No, I know. I'm just saying, if there was such an island...

Friend: But that's just the point. There couldn't be.

Me: Okay, but just supposing there was... I know there couldn't really be such an island, but let's just pretend. If there was an island like that...

Friend: No! It doesn't make sense. You want me to do a logic problem with an illogical premise!

Me: Well, the premise is fictional, but you can still deduce things from it. I mean, people can't fly, but if I said, "Imagine people could fly: what would happen if one crashed into the blades of a helicopter?", you could answer the question.

Friend: Fine. What was the question, again?

Me: There's this island, and... [I explain it again.]

(Pause.)

Friend: You know what I think?

Me: No. What?

Friend: I think people make things like that up ON PURPOSE!

(Pause.)

Me: Um... Well... yeah. I mean, it is made up. A logic professor made it up.

Friend: Jesus Christ! Aren't there enough problems in the world without people adding more?!?

I've had many discussions like this, and there seem to be two major disconnects:

1) It's pointless to derive logic from an illogical premise.
I think that's wrong, but I wonder if the other view is a confusion or a matter of taste. It might be a confusion. As others have pointed out, we use the word "logic" to mean more than one thing. The danger is using it in multiple ways at once. But if it's a matter of taste, my friend might have just been saying, "Why waste brain cells solving a problem that could never actually arise in the real world." I can't answer that, other than to say that, for me, it's fun. It's fun in the same way that fictions is fun. One could certainly say, "Why bother watching 'Jaws'? It's all made up?"

2) It's pointless and irresponsible to make up problems where none exist.
Again, I can't refute this. It's a matter of taste. Why play baseball? You don't have to.

I do think that logicians and math teachers could help by being really clear why they make up nonsensical islands and unexpected hangings. It's not to make up a crazy scenario. It's because they're trying to make a complex bit of math or logic understandable to laypeople via an analogy.
posted by grumblebee at 12:04 PM on February 15, 2008 [9 favorites]

But this seems to fall apart in assuming there are only 2 choices in eye color. And in reality, there are N choices. And at no point are these highly logical people let in on what N is.

Instead of thinking in terms of blue and brown (and red, green, taupe, whatever), you can always get a 2 choice system in terms of blue and not blue. This'll work just as same as the blue/brown thing in the wording of the question, so long as people are told that there is one blue eyed person.
posted by Schismatic at 12:06 PM on February 15, 2008

HI I'M ON METAFILTER AND I COULD OVERTHINK AN ISLAND OF LOGICIANS.
posted by empath at 12:06 PM on February 15, 2008 [1 favorite]

Ok, yeah, it's death all around.

Let me explicate in detail for n = 4

Day 0
Foreigner's State of the Union address
A sees B,C,D.
A expects B to see C&D and avoid suicide. Similar for others.
A expects B to expect of C & D that each will expect the other to commit suicide.

Day 1
No suicides.
A expects B to expect C & D to be surprised of the other's existence and to commit suicide thereafter.

Day 2
No suicides.
A expects B to be surprised and reason that B himself is blue-eyed and commit suicide.

Day 3
No suicides.
Oops!
posted by Gyan at 12:11 PM on February 15, 2008

let me see if I understand this solution:

if one blue eyed islander existed, he would not previously be aware that any blue eyed islanders existed at all, so when the foreigner says that there is one, he realizes it must be him since he knows that everyone else is not blue eyed. he kills himself.

if there are two, then each blue eyed person will assume that the other one should have killed himself by the next day. when the other one does not, they both think "he must think there's another blue eyed islander. since I know no one else has blue eyes, that islander must be me!" they both kill themselves on the second day.

if there are three, then they each think "okay, those two guys don't realize they have blue eyes because they think the foreigner is talking about the other one. so they're going to expect the other one to kill himself on the next day. when that doesn't happen, they're each going to realize that it's because the other one sees another blue eyed islander that they assume the foreigner is talking about and that since no one else has blue eyes it must be them. so on the day after THAT realization, the second day since the announcement, they'll both kill themselves." when that doesn't happen, each of the three islanders realizes that it's because they were each expecting the two islanders they knew about to kill themselves on the second day. when that doesn't happen, they each realize that it's because there was a third islander, namely themselves, that they each didn't know about that was affecting the other two islanders' expectations, and they all kill themselves.

here's where I differ:

if there are 5 islanders, then things change. because the previous four all hinge on the idea that from the perspective of a blue-eyed islander that there is one islander who has a reason to kill himself. to be clearer, it all depends on what each islander THINKS another islander sees, but ONLY one blue-eyed islander iteration lower than their own. so if we're talking about one of 5 blue eyed islanders, it all depends on what each of those islanders would think a blue eyed islander sees if there are only 4 blue eyed islanders, NOT what they would think if there were only 3, 2 or 1 blue eyed islander. This is because each islander knows the total number of blue eyed islanders can only vary by one islander from what they see, if it varies at all.

If you have a 5th blue eyed islander, he knows that the other 4 all see either 3 or 4 other blue eyed islanders. he is aware of the possibility of his being blue eyed, but not its certainty. More importantly, each islander knows what all of the other islanders see and what they can expect the OTHER islanders to see and that they cannot see less than 3 islanders. if the 5th islander thinks the 4th islander only sees 3 islanders, he knows that the third islander ALSO sees at least 3 islanders. since the 5th blue eyed islander sees the same thing all the other blue eyed islanders see, all of the blue eyed islanders know that each OTHER islander sees no fewer than 3 blue eyed islanders. And that's what's important. They all know that no one sees 2 islanders, and no one sees 1, and no one sees 0. Every single islander knows that every single OTHER islander already knew there were blue eyed islanders. No one is expected to commit suicide. without that expected suicide (which depends on at least one islander thinking only one or no other blue eyed islanders exist), there can be no massive blue eyed funeral.
posted by shmegegge at 12:12 PM on February 15, 2008 [3 favorites]

I think that's wrong, but I wonder if the other view is a confusion or a matter of taste.

Nah, just brains being wired differently. As soon as you start applying the logic concepts in this puzzle, it's immediately going to throw some people, 'cause they're not wired for logic, full stop. It's just not gonna fly.
posted by Brandon Blatcher at 12:17 PM on February 15, 2008

to be clear, where this differs from 4 blue eyed islanders is that with 4 of them each blue eyed islander (BEI) thinks the other three only see 2 BEIs. It's that distance from seeing only 2 BEIs that is important. if you think the other BEIs only see 2, then those 2 can expect each other to die. If you think the other BEIs see 3 or more, then none of them can expect any of the others to die, because none of them think that anyone else thinks that anyone is being surprised by the knowledge that there are blue eyed islanders on the island.
posted by shmegegge at 12:23 PM on February 15, 2008

As soon as you start applying the logic concepts in this puzzle, it's immediately going to throw some people

It's funny, though: I'd say my mind IS wired for logic, but the first thing I do when I come across a problem like this is to try to abstract it away from the story. A, B and C are much easier to understand (in this context) than "islanders."

The "illogical" people get confused because they get wrapped up in pointless details of the story (e.g. no one would ever believe in such a religion). I get confused by the details too -- or worry that I might get confused by them. The difference seems to be that I have some skill for abstracting key info from the story. Or maybe it's just that I care to do so.

It does make me wonder about the point of phrasing these problems as stories. Almost everyone here immediately abstracts away from them. I guess the story is a hook to get you interested.
posted by grumblebee at 12:27 PM on February 15, 2008

By the way, is there really anything paradoxical here or open to interpretation?

The facts are pretty clear: 1000 people, 900 with brown eyes, 100 with blue eyes. People can know anyone's eye-color except his own (each person can know 999 eye colors). If a person knows his eye-color, he dies. A stranger implies there's a blue-eyed person on the island. There are a series of iterations (days).

Couldn't this be modeled on a computer?
posted by grumblebee at 12:31 PM on February 15, 2008

shmegegge: You almost had me with you, but I think you're wrong.
So I'm BEI #5. I see 4 BEIs. I believe that every BEI sees 3 BEIs. I then believe that those 4 BEIs believe that each of the three BEIs they see see only 2 BEIs. And I believe that the four believe that the three believe that the two believe that there is only one.
So, I see 4. I think the 4 see 3, because they don't see me and they don' see themselves.
I think the 4 think the 3 see 2, because they don't see the fourth, or themselves, or me (I think the 4 are wrong about this, and that everyone actually sees at least 3, but the fact that they're wrong doesn't change the fact that they believe it.)
It's not about what people see, or about what people think other people see, it's about what people think other people think other people see.
posted by agentofselection at 12:34 PM on February 15, 2008 [2 favorites]

People can know anyone's eye-color except his own

That will throw people because in the real world, how could someone NOT know their eye color?
posted by Brandon Blatcher at 12:35 PM on February 15, 2008

I think XKCD's version (also linked in the original website) has a much cleaner and understandable logic to it. There, the people are equivalent to logical robots, and there is no taboo about the subject of eye colour.

To me, it is those two aspects that make the linked logic puzzle flawed, in addition to the inherent flaw in the set-up - namely that if these islanders are highly logical, one of the very first things that they would say to any outsider is "Don't tell anyone what their eye colour is, otherwise they will have to kill themselves!"

Leaving that flaw aside, by making the islanders devout and making the subject of eye colour taboo, you are creating a situation in which logical inference is possible, but not required. The islanders COULD count to "pronouncement day + all the blue eyed islanders I see", and see if there are suicides, but because they are devout and the subject is taboo, they would, in the wording of the logic puzzle simply accept that they see many with blue eyes, and thus remove any NEED to seek out the colour of their own eyes, which is taboo anyway. Thus, no suicides ever (though I agree with milarepa that the foreigner is toast).
posted by birdsquared at 12:36 PM on February 15, 2008

Ok, I just got back from my lunch run where I thought about this. Here's how I'm now thinking about it.

The same as before, really, but I've named things.

One blueeyed islander kills themselves the next day. (L1, the logic of one.)

Two each expect the other to kill themselves the next day, an expectation that goes unfulfilled, so they both do it day 2. (L2, the logic of two)

Three each expect that the other two are operating by L2, but no deaths on day 3 means there are more than 2 blueys, which means L3, and deaths on the third day.

Four each expect deaths on the third day due to L3, when they don't happen, it's L4.

Five each expect deaths on the fourth day, but L5.

Etc, ad suicidum. Note that brownies all expect day on the day it does end up occurring, and so do not kill themselves.

Another way to think about this is to operationalize the stricture to suicide, such that if expected suicides don't occur by 12:01 pm on the day of expectation, a removed entity (God) calls out "Do it already!" at 12:02 pm. If you're a blue-eyed observer expecting deaths on day four (because you see four blueys), and you don't hear that pronouncement from on high, you know you're blue eyed. This doesn't change the puzzle at all, but it does remove the problem of suicidal logic for all who are actually having trouble with that.
posted by OmieWise at 12:37 PM on February 15, 2008

mr_roboto: See here. And to restate for anyone who hasn't gotten it: the new information that the foreigner brings is not that there are blue-eyed islanders, which they knew, but that the existence of such is common knowledge. Read the Wikipedia article and think about it again.

I can read it all day long but so what? Having common knowledge is not the reason for killing yourself. They don't kill themselves for knowing what other people's eyecolor is, they do it for knowing their own. The foreigner's words do not tell any individual what their own eye color is, only that there is another person with blue eyes, something everyone already knows. One cannot assume that one's own eyes are blue simply based on the knowledge that someone in the set's eyes are blue, particularly when faced with the already established fact that someone's eyes are blue.

Or, what shmegegge said.
posted by Pollomacho at 12:40 PM on February 15, 2008

There's a pretty big difference between the problem posed on terrytao and the problem on Wikipedia: on terrytao, everyone must act if they know their eye color; on Wikipedia only the blues must act. At first glance, I would think that knowing the browns are going to act makes the logic a little different from knowing only the blues will act.
posted by forrest at 12:43 PM on February 15, 2008

I don't understand why you think there is a logical deadlock. I didn't understand your explanation of that deadlock.

The solutions for N < 4 all rely on an individual either a) being able to deduce that they are blue eyed, or b) being certain that someone else should have been able to deduce that they were blue eyed.

So, let's reduce to 5 people on the island. Four blues and one brown (A, B, C, D, and E)

Day 0 thinks:
quonsar says "I'm glad to see a blue eyed person".

A: "I'm not certain whether I'm blue-eyed because he's referring to B, C, or D or possibly me (A). However, B is thinking that he's talking about C or D or possibly me (A), so B has no reason to commit suicide. Similarly for what C and D are thinking. E is thinking that quonsar is talking about B, C, D, or possibly me, so he also has no reason to commit suicide."

B: ...
C: ...
D: ...
E: "quonsar is referring to A, B, C, D, or possibly me (E). Also, A, B, C, and D are thinking exactly what comes after the A: a few lines above here."

Net results: A, B, C, D, E all realize that none of the others have the information necessary to deduce anything with certainty. No certainty == no suicides.
posted by tkolar at 12:44 PM on February 15, 2008 [1 favorite]

I think the problem that shmegegge is getting at is that you should not be starting the inductive case in the first place. This is also what people are implying when they ask why the islanders haven't simply killed themselves off already: since everyone already knows that there are blue-eyed people on the island, and multiple blue-eyed people on the island, the information is not a surprise. The "clever" part of the logic game is that the new but not surprising information creates a base from which induction can begin. The problem is in the status quo ante: the base case for induction should have happened when the religion was founded or the islanders first settled the island, not when the announcement was made.
posted by graymouser at 12:45 PM on February 15, 2008

Interestingly, it's only death all around if everybody hears the stranger. Otherwise, the induction won't hold: the 100th blue-eyed islander can't say: "but he didn't kill himself, which (if I had brown eyes) he would have!" Because he might not have heard.

But even if everybody knows, everybody has to know that everybody knows--since this 100th islander needs to know that the 99th islander heard. But the 99th islander, were he to have killed himself, would have to have known that the 98th islander also heard the stranger! So everybody has to know that everybody knows that everybody knows! This goes on all the way down to n iterations, where n is the number of people.

What is really needed is common knowledge that there is a blue-eyed person on the island. That's why this logic puzzle (and its variants) are often used as illustrative examples of what "common knowledge" is and how it differs from "mutual knowledge" (before the stranger came, the islanders had mutual knowledge that there was a blue-eyed person on the island, but not common knowledge). More from the Stanford Encyclopedia of Philosophy.
posted by goingonit at 12:46 PM on February 15, 2008 [2 favorites]

Oops! Missed the spoiler...
posted by goingonit at 12:47 PM on February 15, 2008

Sorry, hit post too soon. I was going to add that, with terrytao's version, if a brown is able to deduce his eye color, he's going to kill himself. The knowledge that browns are/aren't acting -- and that they possess the same powers of deduction as the blues -- will have an effect on how the blue thinks. Browns have the same behavior as blues in terrytao; only the eye color differentiates the two groups. In Wikipedia, both eye color and behavior are different.
posted by forrest at 12:48 PM on February 15, 2008

grumblebee: I suddenly feel fortunate that I'm surrounded by puzzle- and game-fans. A friend who reacted that way when I tried to present a fun logic puzzle to them would quickly become an unfriend.

Now, if we all lived on an island where everyone was required to kill themselves if they ever figure out whether or not they're my friend...
posted by rifflesby at 12:51 PM on February 15, 2008

No one gets new information from the traveler. Instead, people think that other people think that other people think... that people got new information. Number 5 expects the 4 to expect the three to expect the two to expect the one to be surprised. 5 expects the 4 to expect the 3 to expect the 2 to be surprised when the 1 is not surprised. 5 expects the 4 to expect the 3 to be surprised when the 2 are not surprised. 5 expects the 4 to be surprised when the 3 are not surprised. 5 is surprised when the 4 are not surprised. 5 (and all 5 of them are number 5) kills himself.
So, what the traveler does is shift everyone's expectations to this. Previously, 3 thought 2 thought 1 thought 0. Now when the traveler comes, 3 thinks 2 thinks 1 thinks 1.
That is the change in information.
posted by agentofselection at 12:53 PM on February 15, 2008 [2 favorites]

What's with the 24-hour waiting period between suicides? 1-suicide-per-day is not written into the question, so why is it assumed?

It's not one suicide per day, it's one scheduled slot for however many suicides, scheduled at the same time each day. It's just there to make the iteration of the induction explicit; it could be made to be something that happens every minute or every month, but a day is a nice middle point: long enough to work out the deadly implications between iterations, short enough to limit somewhat the human complications of natural birth and death and so on.
posted by cortex at 12:53 PM on February 15, 2008

tkolar-As formulated, you're seeing the problem as too static. It evolves over time. Suicide would not be a certainty on day 1 because of the scenario you outlined, but no one would expect it to be, either. The reality is that person A expects suicides on day four, because he can see four blue eyed people and the rest not. When those expected suicides don't occur, and A can only see four blue eyed people, A must be blue eyed.

It's a set of nested logic problems. For each n bluies, they expect deaths at day n-1 because they expect that each person they see expects deaths at n-2 and will commit suicide on n-1 when they don't see that.

The World Famous:
Seriously, what's with the "one blue-eyed islander kills themself the next day?" How does he know he's blue-eyed? Why wouldn't a brownie reach the same conclusion, albeit erroneously? How would anyone know whether their conclusion was in error or not?

While I'm not 100% convinced by my own arguments, yours make no sense at all. If the stranger says that they see a blueyed person, and there is only one, that blueeyed person will only see people without blue eyes, and will know to commit suicide. This is not open to doubt. Similarly, if there is only one bluey each brownie will see one bluey, and will not commit suicide. That is not open to doubt.
posted by OmieWise at 12:55 PM on February 15, 2008 [1 favorite]

The World Famous: okay, so you agree with the conclusion for n=1, but disagree for n=100. Do you agree or disagree for n=2? n=3? n=4?

On preview: No, the browns have different information from the blues, so reach a different conclusion.
posted by agentofselection at 1:00 PM on February 15, 2008

The reason this problem is counter intuitive is that it seems that the foreigner brings no new information. He is telling them that there is at least one blue eyed person, which they are all well aware of.

Actually he does bring new information. I think it easier to see this if you turn the problem around, and look at what the situation is before the foreigner arrives.

Start with 2 blue eyed people, A and B.

A thinks:

If I am a brown eye, then B might think that there are no blue eyed people on the island (or just one)

Or if I am a blue eye, then that guy thinks that there is at least one blue eyed person.

When the foreigner arrives, and says that there is at least one blue eyed person, the situation changes. The possibility that the other guy thinks that there are no blue eyed people disappears. It is this the disappearance of this possibility that causes the induction to get started, and results in the suicide after 2 days.

It is the n=3 case where things get complicated:

3 blue eyes, call them A, B and C.

A looks at B and thinks.

I might be brown eyed. Also, B might think he might be brown eyed. So B might think that C doesn't know that there are blue eyed people on the island.

Of course B doesn't think that, because A is blue eyed, but A doesn't know that, so its a possibility in A's mind.

obviously this is only one possibility, but with the arrival of the foreigner it becomes an impossibility. This is the new information that the foreigner brings, and it is true for any n.

for n=4

A thinks

B might believe that C might believe that D might believe that there are no blue eyed people on the island.

In other words, until the foreigner arrives, it is possible to say:

There might be someone that thinks, that someone else thinks, that someone else thinks, .... , that someone else thinks that there are no blue eyed people on the island.

The fact that this is no longer possible after the foreigner arrives is what gets the induction going.

I don't know if that helps, but that's my best attempt at explaining the seeming contradiction.
posted by Touchstone at 1:02 PM on February 15, 2008 [4 favorites]

Why don't the islanders just trade for what's behind door number 3?
posted by turaho at 1:03 PM on February 15, 2008

The key - After the visitor speaks there is the potential for new information to be learned each day. It's only on the 100th day that you know what all the other blues know - That they see the same thing you see.

Before that day you can assume they don't see the same thing you see. You can assume they see 98 blues, while you see 99.

The new information the visitor brings is a start date. But that new information isn't useful until day N, where N is the number of blues.
posted by Ragma at 1:06 PM on February 15, 2008

There's not much to do. They're highly numerate. The deathly prohibition against eye-color knowledge has turned them into obsessive eye-watchers.

If they had the inclination to figure out what the color of everyone's eyes was they could just ask each other "Hey, what color are my eyes?" Since they have not done so (and consequently offed themselves prior to the visitor's arrival), they clearly have no such inclination, i.e. their devoutness neither impels nor requires them to seek out information about eye color. Being perfectly logical, they should know that counting is tantamount to asking someone what your own eye color is, because you know that once you've counted you can induct. So by that same token, if they wouldn't ask someone else, then they wouldn't count either.
posted by juv3nal at 1:07 PM on February 15, 2008

TWF: which hypothetical? In the 1 BEI version, I think it's obvious how they have different information. The browns see 1, and don't need to kill themselves. The blue sees none, knows it's him, kills self.

In the 2 BEI version, the browns see 2, the blues see 1. The blues expect the one to kill himself. The blues don't kill themselves. The blues realize that there are more than one blue. Seeing only one, they realize they must be blue, kill themselves. Repeat.
Browns always see one more than blues.
Y'know, maybe you should re-read the full explanation at the links, actually. You're arguing from a point that even the others who disagree with the linked solution disagree with.
posted by agentofselection at 1:08 PM on February 15, 2008

OmieWise wrote...

tkolar-As formulated, you're seeing the problem as too static. It evolves over time. Suicide would not be a certainty on day 1 because of the scenario you outlined, but no one would expect it to be, either.

In fact, to be clear, they would be certain that there would NOT be a suicide.

The reality is that person A expects suicides on day four, because he can see four blue eyed people and the rest not.

You've kept making this assertion and I'm not following where it comes from.

If no one of the three blueyed people I can see were certain enough to kill themselves on day one, what's going to change their minds as time passes? And as long as they haven't changed their minds, why should I?
posted by tkolar at 1:10 PM on February 15, 2008

I wrote...
The reality is that person A expects suicides on day four, because he can see four blue eyed people and the rest not.

And that should have been italicized above, too. :-)
posted by tkolar at 1:11 PM on February 15, 2008

dw: Everyone's eyes are either blue or non-blue, so in that sense there are only 2 choices.

But "non-blue" doesn't count! "My eyes are not blue." Well, great. So what color ARE your eyes?

This problem doesn't work because there are N colors. The traveler only states that ONE person is of ONE color. And the whole chain of events is reliant on what ultimately is a conjecture.

Honestly, if they looked at their own kids and saw the patterns that emerged from genetics, the island would have Jonestowned already. Even if they didn't know jack about it, they'd still be able to figure it out in the same way they figured it out with this 100 days o' killing.
posted by dw at 1:12 PM on February 15, 2008

If they had the inclination to figure out what the color of everyone's eyes was they could just ask each other "Hey, what color are my eyes?"

The problem dictates that their religion prohibits discussing it, and it dictates that they are devout. They won't discuss it. The foreigner, unfamiliar with this prohibition, transgresses.
posted by cortex at 1:13 PM on February 15, 2008

tkolar: I, as the 5th BEI, don't expect a suicide on day one. I expect other people to expect other people to expect other people to expect a suicide on day one.
I expect, through these iterations, that there will be suicide on day four, because I expect other people to expect suicides on day 3.

For a full a-thinks-b-thinks-c-thinks-d-thinks iterative explanation, see my earlier comments.
posted by agentofselection at 1:13 PM on February 15, 2008

So I'm BEI #5. I see 4 BEIs. I believe that every BEI sees 3 BEIs. I then believe that those 4 BEIs believe that each of the three BEIs they see see only 2 BEIs. And I believe that the four believe that the three believe that the two believe that there is only one.

I don't think it works that way.

Someone mefimailed me a way to think about this a little more clearly that I'm going to adopt a bit.

I'm 5.

I see 4321

I believe that 4 sees 321.

now, it's really easy to say this:

I believe that 4 believes that 3 sees 2 and 1.

I believe that 4 believes that 3 believes that 2 sees 1.

I believe that 4 believes that 3 believes that 2 believes that 1 sees none.

But then we're ignoring the rest of what I see, as 5.

Because I believe that 4 believes that 3 sees 21.

And I also believe that 3 believes that 4 sees 21.

I also believe that 2 believes that 3 sees 41 and 4 sees 31.

And I also believe that 1 believes that 2 sees 34, 3 sees 24, and 4 sees 23.

I do not believe that anyone believes that anyone else sees only 1 or none blue eyed people. So, since my own suicide depends on the believing 4 will commit suicide, the chain breaks. I don't believe 4 will commit suicide because 4 already knows that 2 and 1 will not, and so does 3 and 2 and 1. 4 already knows that 3 will not commit suicide because he knows that 3 knows 2 and 1 will not. 4 also knows that 2 will not commit suicide because he knows that 3 and 1 will not. And 4 knows that 1 will not commit suicide because he knows that 2 and 3 will not. Because I know that 4 knows all this, I know that 4 does not base his eye color on their suicides or lack thereof because he knows their lack of suicide will be based on seeing each other whether his eyes are blue or not. No one sees no other blue eyes. It's hard to wrap around, but i'm pretty sure it's true.

going the way I did it in blockquotes is what I'm going to call the math way of doing things.
posted by shmegegge at 1:15 PM on February 15, 2008 [1 favorite]

More from the Stanford Encyclopedia of Philosophy.

OK, the Barbecue Problem is a better explanation, since it does work with a binary supposition.
posted by dw at 1:16 PM on February 15, 2008

dw: it doesn't matter how many colors of eyes there are. What matters is how many blue-eyed people there are. If you know there to be 100 blue eyed people, and you can only see 99 of them, you must be number 100, even if the island includes people with purple-and-green striped eyes.
posted by agentofselection at 1:16 PM on February 15, 2008

Ah, there's a Stanford Encyclopedia of Philosophy entry on common knowledge! That's great. Time to whittle away more time.
posted by painquale at 1:18 PM on February 15, 2008

um... to finish... (weird) the math way of doing things is to see the problem from the perspective of a series of numbers, rather than a matrix of perceptions. those perceptions change at the point where everyone can plainly see that EVERYONE ELSE can plainly see that no single blue eyed person expects there to be no blue eyed people. that point, near as I can figure, is 5 blue eyed people.
posted by shmegegge at 1:21 PM on February 15, 2008

I think I've roughly figured out what is at least one significant problem in the presentation of the problem (if not in the problem itself). It assumes two contradictory premises.

1. Before the foreigner arrives, the islanders operate on the assumption that not everyone knows that there is at least one blue eyed person.

2. After the foreigner makes his statement, the islanders operate on the assumption that everyone knows the eye color of everyone else on the island except for them, and expects suicide on a given day (the number of other blue eyed people on the island).

Therefore, the "new" information should not be new for n > 1 and the induction should have already played itself out.
posted by graymouser at 1:21 PM on February 15, 2008

shmegegge:
Yes, you can state the fact that I believe 4 sees 321 and 3 sees 421 and 2 sees 431 and 1 sees 432. These are restatements of the same thing, though, it's just as effective to refer to the generic imaginary 3 BEIS and imaginary 2 BEIs.
4 sees 321. 4 thinks 3 sees 21.
3 actually sees 421, but that doesn't affect 4s belief that 3 sees 21.
Similarly, 4 thinks 3 thinks 2 sees 1. This is wrong, but 4 believes it.
4 thinks that 3 thinks that 2 thinks that 1 will kill himself.
3 doesn't actually think this, but that's okay.

You can't keep coming back to what you can see, because the problem rests on what you think other people see, not on what you see.
posted by agentofselection at 1:24 PM on February 15, 2008

Unbeknownist to the islanders, the visitor is from is island where half the people tell the truth all the time and half of 'em lie.

Anyway, my problem with this puzzle is in the solution. The fact that the islanders know the percentage of blue-eyed islanders is assumed there, even though this information wasn't told in the setup. In my experience, lots of these kinds of pass-around logic problems suffer from this kind of flaw.
posted by JHarris at 1:25 PM on February 15, 2008

graymouser: See my earlier explanation of the traveler's effect. He effects what 3 thinks about what 2 thinks about what 1 thinks. Iteratively, this changes what 3 thinks about what 2 thinks, and then changes what 1 thinks. The suicides do in fact depend on the traveler, no matter the n.
posted by agentofselection at 1:27 PM on February 15, 2008

JHarris: no knowledge of percentages is necessary for the solution, though that knowledge would make the solution much easier, and not require the traveler.
posted by agentofselection at 1:28 PM on February 15, 2008

Therefore, the "new" information should not be new for n > 1 and the induction should have already played itself out.

Incorrect: and this is the crux of the matter.

If n=2, each blue-eyed person can allow for the possibility that they are brown-eyed, and that the other blue-eyed person's reasoning could be playing out as in the n=1 case (i.e. there is no knowledge of the existence of blue-eyed people).

If n=3, each blue-eyed person can allow for the possibility that they are brown-eyed, and that the reasoning of each blue-eyed person they see is playing out as described in the n=2 case.

If n=4, each blue-eyed person can allow for the possibility that they are brown-eyed, and that the reasoning of each blue-eyed person they see is playing out as described in the n=3 case.

And so on.

Once the visitor introduces the knowledge of the existence of blue-eyed people, this chain of reasoning fails, and the dying starts.
posted by mr_roboto at 1:28 PM on February 15, 2008

What different information do they have?

Before the visitor speaks, each blue-eyed person knows "there are either 99 or 100 blue-eyed people on the island." Each non-blue-eyed person knows "there are either 100 or 101 blue-eyed people on the island."

----

As to what new information the visitor brings: the key is that the visitor tells everyone together. That means the visitor is actually conveying an infinite set of information, of the form:
- At least one islander has blue eyes.
- Everyone knows that at least one islander has blue eyes.
- Everyone knows that everyone knows that at least one islander has blue eyes.
- Everyone knows that everyone knows that everyone knows that at least one islander has blue eyes.
- Everyone knows that everyone knows that everyone knows that everyone knows that at least one islander has blue eyes.
Ad infinitum

Some of the items in this series were already known to the islanders, but some were not.

In the case of only a single blue-eyed islander, A, the information "at least one islander has blue eyes" is news to A, so he offs himself on day 1.

With 2 blue-eyed islanders, "At least one islander has blue eyes" is not news to anyone. But "Everyone knows that at least one islander has blue eyes" is news to A and B; A did not previously know that B knew that at least one islander had blue eyes, and vice versa. Now A knows that B knows that at least one islander has blue eyes; since B did not kill himself on the first day, A knows that "At least one islander has blue eyes" was not a surprise to B, and kills himself on day 2.

With 3 blue-eyed islanders, "At least one islander has blue eyes" is not news to anyone. Nor is "Everyone knows that at least one islander has blue eyes." (A sees two other blue-eyed islanders, B and C, so A knows that everyone on the island, including B and C, already konw that at least one person has blue eyes.) "Everyone knows that everyone knows that at least one island has blue eyes" is new information to A, B, and C, however.

With 4 blue-eyed islanders, "Everyone knows that everyone knows that everyone knows that at least one person has blue eyes" ("Everyone knows that³ at least one person has blue eyes") is new information to the blue-eyes.

With 100 blue-eyed islanders, "Everyone knows that⁹⁹ at least one person has blue eyes" is new information to the blue-eyes. This is the new information the visitor brings.

Further evidence in support of this: if the visitor went to each islander individually and told them "At least one person on the island has blue eyes," but never said anything about what he told the other islanders, and the islanders never talked among themselves about what the visitor told them, no one would ever kill themselves, unless there were only a single blue-eyed person to start with.
posted by DevilsAdvocate at 1:29 PM on February 15, 2008 [5 favorites]

Degrees of freedom
posted by Blazecock Pileon at 1:29 PM on February 15, 2008

If they had the inclination to figure out what the color of everyone's eyes was they could just ask each other "Hey, what color are my eyes?"

The problem dictates that their religion prohibits discussing it, and it dictates that they are devout. They won't discuss it. The foreigner, unfamiliar with this prohibition, transgresses.

My bad. Missed that can't talk about it bit.
posted by juv3nal at 1:30 PM on February 15, 2008

To be clear, there's no chain of suicides. All the blues think the exact same thing, and all the browns think the same thing. All the blues think there are 99 blues, who will kill themselves on day 99. The browns think there are 100 blues who will kill themselves on day 100. The browns are right.
The chain reaction is only in what people think that other people think; the action all takes place at once.
posted by agentofselection at 1:32 PM on February 15, 2008 [1 favorite]

agentofselection,

no, I get that the numbers are interchangeable. that's what makes me right, i think. that's what people keep forgetting when they do the problem. that's why they keep NOT coming back to what the root observer sees.

all suicides in this problem depend on one BEI not knowing that anyone on the island has blue eyes. this is important. it's the most important thing. at 5 BEIs, each one knows that the other 4 can't expect any of the other 3 or possibly 4 to believe that.

at 4, it's possible for each BEI to believe that the other 3 only believe that there are 2 BEIs. if there are only 2, then one can be expected kill himself when the other one does not. It could be common knowledge that there are BEIs at all, but it might not be.

at 5, each BEI knows that the others all know for a fact that there are at least 3 BEIs. because he can see 4 BEIs looking at the other 3. they all know at that very moment that which BEI is being referred to by the foreigner is unknown, and none of them are surprised to find out that there are BEIs in the first place. This means that it's KNOWN that the existence of BEIs is common knowledge. So not only do they know that there are BEIs, they know that everyone else knows it, too. It changes the opening dynamic of the situation. No single BEI is expected to commit suicide by anyone, because they all already knew about BEIs.
posted by shmegegge at 1:37 PM on February 15, 2008

Let me just point out that this is the EXACT reason for the Prime Directive.
posted by Astro Zombie at 1:40 PM on February 15, 2008 [3 favorites]

Ah, shmegegge, this is METAfilter. You gotta get more recursive. So, N=5. No BEI believes that someone could believe that there are only 3 BEIs (your reasoning.) But he does believe that someone else could believe that someone could believe it.
posted by agentofselection at 1:43 PM on February 15, 2008

the problem i'm having is that the islanders are all highly "Logical" AND highly "Devout."

Simple. Their god exists and will subject them to something inarguably worse than death if they do not comply with the edicts of their religion, and this has been empirically proven to them.
posted by Durhey at 1:46 PM on February 15, 2008

Here's my take on this.

When the visitor announces that someone has blue eyes, he in essence saying "if you people are logical enough to take my statement to its logical conclusion, at least one of you will kill themselves." So that's the new information. In other words, there's always been a bomb sitting on this island; the visitor merely lights the fuse.

Okay, so the visitor makes his announcement on day 0. Let's follow the thought process of everyone on the island.

If there's only one blue eyed guy on the island, of course he's killing himself on day 1. He doesn't see anybody with blue eyes, so he knows he must be the one and will kill himself the next day as his beliefs dictate.

If there are two guys with blue eyes, neither of them kills themselves on day 1 because they each see a guy with blue eyes and they know that that if he is the only guy with blue eyes he'll kill himself on day 1 (cf. previous paragraph). So day 1 passes and neither guy kills himself. A new piece of information is introduced. There are more than one blue eyed guys on this island. So each blue eyed guy now looks around and only sees one other blue eyed guy, thinks oh shit I'm the other blue-eyed guy and kills himself the next day.

Okay, let's say there are three guys with blue eyes. None of them kill themselves on day 1 because they see two other blue-eyed guys and logic dictates that if there are only two blue-eyed guys on the island, they'll kill themselves on day 2 (cf. previous paragraph). So when day 2 passes without suicides, a new piece of information is introduced. There are more than two blue eyed guys on this island. So each blue eyed guy now looks around and only sees two other blue eyed guys, thinks oh shit I'm the other blue-eyed guy and kills himself the next day.

Now there's 4 guys. They each see 3 guys with blue eyes, follows the logic set in the previous paragraphs and decides that if they're the only blue eyed guys, they'll all kill themselves on day 3. When day 3 passes without suicides, a new piece of information is introduced. There are more than three blue eyed guys on this island. So each blue eyed guy now looks around and only sees three other blue eyed guys, thinks oh shit I'm the other blue-eyed guy and kills himself the next day.

Ad nauseum.
posted by turaho at 1:58 PM on February 15, 2008 [2 favorites]

For those who object to the "suicide because of eye color" aspect of the problem, I've heard an alternate phrasing involving marital fidelity instead. By tradition, if a woman on this island finds out that her husband is cheating on her, she kills him -- much more believable, no? Such is the power of the grapevine that everyone on the island knows who's sleeping with whom, with the sole exception that the wife is always the last to know, because no one wants you to murder your husband, however much he deserves it. And the killings are invariably carried out at night, when the husbands and wives are alone together (thus imposing the "next day" rule).

You could also do it with the genders reversed, too, but that's uncomfortably close to reality in some parts of the world.
posted by baf at 1:59 PM on February 15, 2008

No BEI believes that someone could believe that there are only 3 BEIs (your reasoning.) But he does believe that someone else could believe that someone could believe it.

No, my reasoning is that no BEI believes that someone could believe that there are only 2 BEIs.

And he does not beleive that someone else could belive that someone else could believe indefinitely. What he believes someone else could believe stops at 2. The point is that no one can think that anyone else expects a BEI to kill himself.

Think of it this way:

If there's a room full of these dudes. 100 BEIs and 1 green eyed islander (GEI). and someone says "so nice to see so many blue eyed islanders!" how many of them kill themselves? as has been stated upthread, what the man is doing to cause a suicide is making the existence of BEIs common knowledge. But it already was common knowledge. More importantly, it was common knowledge THAT it was common knowledge. No one has any reason to think that someone would be surprised by the info and therefore kill themselves a la the example where one blue eyed islander does. without the expectation of that intitial suicide the whole thing has no effect. so what's the point where that's the case? There must be some number where that happens. I believe that number is 5, for the reasons I've outlined.

Now, believe me, I already get that one islander could believe that one islander could believe, etc... You don't need to repeat it again. I'm saying it doesn't apply for a number of BEIs over 5 because at 5 or more it's plainly obvious to everyone that there are BEIs and everyone knew about them. That being the case no one can be expected to kill themselves when they first hear about it. Not one soul. This is about the existence of common knowledge, not the recursion of suicides or lack thereof.
posted by shmegegge at 2:03 PM on February 15, 2008

I'm not saying someone's expected to kill themselves when they hear about it. No one expects any suicides on day 1. They expect other people to expect, etc.
A can't see A's eyes. A thinks B doesn't see A or B. A thinks B thinks C doesn't see A or B or C.

The fact that (1)everyone knows there are BEIs and (2)everyone knows 1 isn't enough. It needs to be recursed as many times as there are BEIs, as in DevilsAdvocates' post above.

In your 99BEI and 1 GEI party we should still expect 99 suicides 99 days after the announcement, because that's when the knowledge becomes infinitely recursed.
posted by agentofselection at 2:11 PM on February 15, 2008

Hmm, grammatically unclear: I mean the knowledge becomes infinitely recursed at the announcement, not on day 99.
posted by agentofselection at 2:13 PM on February 15, 2008

If there are 3 or more people with blue eyes then no one dies.

Each already knows there are 2 people with blue eyes, therefore when the stranger announces that one of them has blue eyes they just think "ya, it's those guys" and leave it there.
posted by Vindaloo at 2:17 PM on February 15, 2008

Vindaloo: the three believe it's the 2, but they also believe that the 2 believe in 1. The three expect the two to be surprised when the 1 doesn't kill himself, and the three are in turn surprised when the two aren't surprised.
posted by agentofselection at 2:19 PM on February 15, 2008

A can't see A's eyes. A thinks B doesn't see A or B. A thinks B thinks C doesn't see A or B or C

just to be clear, you're making up new rules.

the problem, as explained, implies (as cortex went into way upthread) that they all know who has what color eyes except for themselves. that's why they're all able to deduct their own eye color, supposedly, based on the number of days no one has killed themselves.

The fact that (1)everyone knows there are BEIs and (2)everyone knows 1 isn't enough.

You're right. It's enough that (1) everyone knows there are BEIs and (2) everyone knows 3 of them.

t needs to be recursed as many times as there are BEIs, as in DevilsAdvocates' post above.

No it doesn't, as in my posts above.

In your 99BEI and 1 GEI party we should still expect 99 suicides 99 days after the announcement, because that's when the knowledge becomes infinitely recursed.

that's when it becomes what? it doesn't become infinitely anything, either when the foreigner says it or 100 days later. I would like you to explain the chain of events one person at a time for 99 BEIs killing themselves on an island where there are 99 BEIs and 1 GEI. (I chose green, by the way, just because it abbreviates differently than BEI, which brown eyes do not.) Start with one and go as far as you feel like, because I don't see even one guy killing himself. There's no "I see no BEIs, so I must be the one he's talking about" moment, and no one could expect there to be one, so I don't see how it's possible.
posted by shmegegge at 2:20 PM on February 15, 2008

Breaking down the comment from DevilsAdvocate:

In the case of only a single blue-eyed islander, A, the information "at least one islander has blue eyes" is news to A, so he offs himself on day 1.

Sure.

With 2 blue-eyed islanders, "At least one islander has blue eyes" is not news to anyone. But "Everyone knows that at least one islander has blue eyes" is news to A and B; A did not previously know that B knew that at least one islander had blue eyes, and vice versa. Now A knows that B knows that at least one islander has blue eyes; since B did not kill himself on the first day, A knows that "At least one islander has blue eyes" was not a surprise to B, and kills himself on day 2.

Sure.

With 3 blue-eyed islanders, "At least one islander has blue eyes" is not news to anyone. Nor is "Everyone knows that at least one islander has blue eyes." (A sees two other blue-eyed islanders, B and C, so A knows that everyone on the island, including B and C, already konw that at least one person has blue eyes.) "Everyone knows that everyone knows that at least one island has blue eyes" is new information to A, B, and C, however.

No.

I can't see this. I think this is the solution to a different puzzle. It seems to me that if they know the first two pieces of information, given that they are all logical and devout, they can infer the last one.
posted by East Manitoba Regional Junior Kabaddi Champion '94 at 2:23 PM on February 15, 2008

Why not just do this with Indian Poker. It makes a hell of a lot more sense. Instead of days you have betting rounds, instead of suicides you have folds. Easier to wrap your head around, I think.
posted by empath at 2:25 PM on February 15, 2008

EMRJKC'94 makes a point I've been throwing around in my head, myself. I think the linked article made a situation that doesn't accurately represent a logic puzzle he heard a better version of, once. I could see there being a puzzle where this situation does recurse until everyone with blue eyes dies, but this doesn't seem to be it. this looks more like a game theory problem designed to help students figure out where patterns stop.
posted by shmegegge at 2:27 PM on February 15, 2008

I think this thread serves as a pretty good brute force-test case of this kind of problem.

Of course, now that I've posted this, I have to go kill myself tomorrow.
posted by wobh at 2:28 PM on February 15, 2008 [1 favorite]

I'm not making up any new rules. They can count the number of eyes they see, but not the number that other people see.

Now, for the 99BEI and 1 GEI, just like for the original case, there is no chain of events, only a chain of thoughts. No one expects a suicide on day 1. All 99 BEIs expect 98 suicides on day 98, instead there are 99 on day 99.

Now, I know you asked for the full explanation of 99 and 1, but since that involves writing out "x thought" 5000 times, I'm going to do a case of 5 BEIs and 1 GEI. We can argue later about whether the logic holds, if you want.

I'm going to number the statements. Could you tell me which number you disagree with, or whether you disagree that my conclusion follows?
1.A sees BCDE (also, B sees ACDE. All of the following are interchangeable, as each BEI goes through the same thought process.)
2.A believes B sees CDE
3.A believes B believes C sees DE
(Please note that this is not the same as "A believes C sees DE")
4.A believes B believes C believes D sees E
5.A believes B believes C believes D believes C will suicide on day 1.
6.A believes B believes C believes D and E will kill themselves on day 2.
7.A believes B believes CDE will suicide on day 3.
8.A believes BCDE will suicide on day 4.
9.BCDE do not suicide on day 4.
10. A realizes his previous beliefs were wrong because A in fact is a BEI.
11.ABCDE suicide on day 5.
posted by agentofselection at 2:34 PM on February 15, 2008 [1 favorite]

Shit, line 5. should read:
5.A believes B believes C believes D believes E will suicide on day 1.
posted by agentofselection at 2:35 PM on February 15, 2008

The importance of the infinitely recursed knowledge is in line 5.
If A knows B knows C knows D knows E knows about BEIs, then A can't believe that
5.A believes B believes C believes D believes E will suicide on day 1.
posted by agentofselection at 2:38 PM on February 15, 2008

Just so you guys know all of you laboring meticulously on this logic problem are now disqualified from working on any Republican Presidential campaign. They drug test for this sort of logic thing.
posted by tkchrist at 2:55 PM on February 15, 2008

yeah, sorry, I thought you said A doesn't see B's eyes. read too quickly.

Now, for the 99BEI and 1 GEI, just like for the original case, there is no chain of events, only a chain of thoughts.

look, I want to be clear about this: I get that there's no chain of suicides. I get the recursion. You really really don't need to be repeating that part over and over. I'm serious about this, it's getting silly. Also, a thought or realization is an event. It's just not a suicide. What you described is still a chain of events.

Now, I know you asked for the full explanation of 99 and 1

I said you could stop at whatever point you wanted. I wasn't really expecting 99 thoughts following 98 other thoughts or anything.

Here's what I take issue with:
5.A believes B believes C believes D believes C will suicide on day 1.

(i assume you meant E will suicide on day 1)

Here's why it doesn't work. It's a room full of 99 blue eyes. There's no point where C believes that D believes that E hasn't seen them. It's not possible. To think it is you have to operate under the assumption that 98 people haven't noticed 97 of the other people in the room. This is the problem with extrapolating this theory past 5. It works really really well at 3 or 4 or even lower. But 1 person cannot look at 99 other people and say "that one, number 43, he doesn't know that 98 or 99 of us have blue eyes." without that point in the process, it doesn't work.

here's an example:

you have 5 guys in a room: ned, adam, joe, harry and tom. they are all facing each other, no mirrors the whole deal. they are all wearing a blue sticker on their foreheads and they can all see the others' stickers, but don't know their own. as soon as they find out what their sticker says they have to leave the room. a loud speaker comes on and says "at least one of you is wearing a blue sticker on his forehead." which one(s) do(es) ned think harry expects to leave the room? if your answer is adam, joe and tom you're wrong. because neither adam, joe nor tom has any reason to know what's on their forehead and harry knows it and ned knows harry knows it.

the point is that it seems like it works when you're thinking in numbers, but it doesn't when you realize it's about individual perspective and the intersection of those perspectives.
posted by shmegegge at 2:59 PM on February 15, 2008

I realize I'm belaboring the same point, but it's because you keep making the same error. You say:
There's no point where C believes that D believes that E hasn't seen them. It's not possible.
And the thing is, I never claim this. I claim A believes that B believes this, because A does not have our perfect perspective.

But 1 person cannot look at 99 other people and say "that one, number 43, he doesn't know that 98 or 99 of us have blue eyes."

And you're right about this. But 1 person CAN look at 99 other people and say "they only see 98 people with blue eyes." (Because they don't see themselves)
You never say "they only see 97(or less) with blue eyes." But you do say "Since they only see 98 people with blue eyes, they must think that those 98 people only see 97 with blue eyes."
posted by agentofselection at 3:09 PM on February 15, 2008

Ugh, this is painful, but I may have to disagree with you, Schmegegge (though I wish you were right!).

Each number of BEIs is associated with a scenario. You agree that the 1-4 person scenarios as defined play out in a straightforward way, with suicide on the appropriate day.

When it gets to five, each person knows that there are only 4-5 BEIs. If the 4-person scenario does NOT play out, it HAS to be 5.

Similarly with six. We know the scenario with 5. If the 5-person scenario does not play out, each person must inevitably conclude that there 6 BEIs. And so on.

What do you think?
posted by shivohum at 3:11 PM on February 15, 2008

here's what you're saying except using the names above, and I hope that makes it easier to see why it doesn't work:

ned sees harry, adam, joe and tom.

ned believes harry sees adam, joe and tom.

ned believes harry believes adam sees joe and tom.

ned believes harry believes adam believes joe sees tom.

ned believes harry believes adam believes joe believes tom will leave the room.

and that's the problem. that's not what ned believes. it's not what anyone with the logic we're supposed to expect from the islanders would believe. the only expectation ned is supposed to have is that harry adam joe and tom will all leave at the 4th moment they're supposed to. but why would they do that? because on the third moment they're all supposed to be surprised that the other 3 didn't leave, according to ned's perspective. but why would they do THAT? three of them are supposed to be surprised that two of them didn't leave. but why would they do that? because two of them are supposed to be surprised that one of them didn't leave. but why would they do that? because one of them is not supposed to know that there are blue stickers on anyone's forehead. but which one would think that? ned, harry, adam, joe or tom? the answer is none of them would think that, because none of them can deduce that their sticker is blue from the information "at least one of you has a blue sticker" when everyone they see has one, and they all know it. the only thing they don't know is their own sticker color, and they all know that about each other, too. none of them would have any reason to leave the room.
posted by shmegegge at 3:21 PM on February 15, 2008

[Discussing the 3BEI case] DA: "Everyone knows that everyone knows that at least one island[er] has blue eyes" is new information to A, B, and C, however.

E...94: I can't see this. I think this is the solution to a different puzzle. It seems to me that if they know the first two pieces of information, given that they are all logical and devout, they can infer the last one.

A knows:
P1. At least two people have blue eyes
P2. Everyone knows at least one person has blue eyes (because everyone can see at least one person with blue eyes)

A does not, initially, know:
P3. Everyone knows that everyone knows at least one person has blue eyes (because if B and C were the only two people with blue eyes, B and C could not reach the conclusion P2 above).

A knows P2, B knows P2, and C knows P2; but A does not know that B or C knows P2, B does not know that A or C knows P2, and C does not know that A or B knows P2.

(Aside: I find it fascinating that shmegegge accepts up to 4 BEIs but not 5. I can see how people might get 1 and reject 2+, or get 1 and 2 but reject 3+, but it seems that once most people accept the case with 3, they accept the entire set. I'm not at all clear on the logic shmegegge by which shmegegge accepts 4 but rejects 5; to me that's like saying, "well, I can see how it works out that 36 BEIs would all kill themselves on day 36, but it doesn't apply for 37 BEIs!")
posted by DevilsAdvocate at 3:22 PM on February 15, 2008

shmegegge, did you read the solution here, and how it explains for more than 4 people?

Because as I said, way up in the thread, if this is worked as a logic problem, I believe all the islanders are history, and I think the solution does a good job of showing why.

The flaw in your logic comes in adding components to the logic problem that are not givens, i.e. that only a certain amount of people will go along with the premise before "wising up". Logically, though the problem is stated as applying to people, you cannot put yourself in their place and so what you think you would do in the circumstances does not apply. So saying, "Well, no reasonable person will accept this after such and such n," assumes facts that are not in evidence.

The only way I would accept, given the facts in evidence, that all the islanders do not kill themselves, would be if it were common knowledge on the island that there are more than two eye colors in existence (so that green or hazel might also be a possibility).
posted by misha at 3:25 PM on February 15, 2008

I think agent of selection has the logic wrong, but the right conclusion. shmegegge is, of course, correct, that the recursion doesn't operate at the level where everyone is looking at everyone else, but I don't think it need to.

I'm going to go over my take again, building up from 1. The question is if it breaks down at some n<1>because they are assuming the two they see each only see one blue. When no deaths occur, it's clear that there must be a third blue, and that the observer is it, so suicides occur on day three.

4) Four blues see three blues apiece. If no one kills themselves on day three, that must mean there are more than three blues, hence suicides on day four. (Note that it does not matter which one of the four you are, you still see three blues, and still expect them to act as three blues would act, and when they don't it reveals your eye color.)

5) Five blues each see four apiece. Their expectation is that the fours will suicide on day four, because that's the consistent logic of four blues. If they don't, that means that there is a fifth, who must be the observer (who, again, in each case is a different blue, but so what). Suicides on day five.

6) etc.

There are several keys to the chain. The most important is the expectation of suicides (from the point of view of any blue observer) on day n-1. Browns have the same expectation, but for day n, and their is borne out. The second key is that the lack of suicides provides assured evidence of the blue observers eye color. I really don't understand why this fails.

tkolar:
If no one of the three blueyed people I can see were certain enough to kill themselves on day one, what's going to change their minds as time passes? And as long as they haven't changed their minds, why should I?

When n>1 then everyone is certain they don't have to kill themselves on day one. They do change their mind when they find that there were not suicides on the day they expected them by counting blue-eyed people. That must mean they have blue eyes. That's why there's enough certainty to commit suicide.
posted by OmieWise at 3:25 PM on February 15, 2008

All this is fine and good, but we don't know enough information, therefore, it should be considered a "mind numbing" problem, not a mind bending one.

If,
posted by Chuffy at 3:28 PM on February 15, 2008

I claim A believes that B believes this, because A does not have our perfect perspective.

I know, but I'm addressing things from A's perspective, not ours. Seriously, go back over my comments, you'll see. A can see that no one can isolate someone who didn't know about the blue eyes, that's why it falls apart.

But 1 person CAN look at 99 other people and say "they only see 98 people with blue eyes." (Because they don't see themselves)

No they can't, and they wouldn't. They'd say "they see 98 OR 99 people with blue eyes."

again, I can't stress this enough: the problem is not about following the recursion. that's the error you keep making. it's about the introduction of new information to one BEI about his own eye color. The only way(s) that can happen is if one BEI somewhere in the room does not know about BEIs, or if a second BEI can believe that the first one doesn't know about BEIs. With any number of 5 or above, that's not possible. There is no point where any of the BEIs can be expected to think "what does he mean blue eyes? no one has blue eyes! oh wait, I must be the one!" because not only would every islander know that there were blue eyes, but they'd all know that all the other islanders know. that's where it ends.
posted by shmegegge at 3:29 PM on February 15, 2008

misha,

thanks for the link. I couldn't find the xkcd solution when I looked for it. the problem is that he brings up the problem I have with it (it's number 2 on his list) and says that he won't provide the response to that issue because he wants us to play around with it in our heads. so I'll happily agree with whatever the solution is, but I haven't seen it, yet.

but I have to leave work now for home. it'll be hours before I'm back if I remember to come back at all. later, folks, and thanks for the discussion. hopefully I'll remember to come back.
posted by shmegegge at 3:35 PM on February 15, 2008

ned sees harry, adam, joe and tom.

ned believes harry sees adam, joe and tom.

ned believes harry believes adam sees joe and tom.

ned believes harry believes adam believes joe sees tom.

ned believes harry believes adam believes joe believes tom will leave the room.

As I said, I think this is a poor way to formulate the problem. I'll reformulate it with names, though, adding jane.

Ned looks around and sees only brown eyes, kills self. Jane sees what she expects.

Ned and Harry both look around and see that the other has blue eyes, they expect death and do not see it, so both kill themselves day 2. Jane sees what she expects.

Ned sees that Harry and Adam have blue eyes (and vice versa x3). They all expect death on day 2 as the logic above dictates, but they do not see it, so all three realize that there is a third blue eyer and all off themselves day 3. Jane sees what she expects.

Joe sees that Ned, Harry and Adam have blue eyes (and vice versa x4). All expect death on day three as per above, and when they don't see it, they all commit suicide on day 4. Jane sees what she expects.

Tom sees that Ned, Harry, Adam and Joe all have blue eyes (and vice versa x5) and expects deaths on day 4 as above. When he does not see them he knows that he too has blue eyes, and all kill themselves on day 5. Jane sees what she expects.

The only expectations are that there will be a suicide on the day equal to the number of blue-eyed folks that you see, because logic dictates that there will be.
posted by OmieWise at 3:35 PM on February 15, 2008

They'd say "they see 98 OR 99 people with blue eyes."

97 or 98. Since they must consider 97 as a possibility, they assume that the other people are behaving as if there are 97. Who therefore in turn must consider 96 to be a possibility. All the way down to one, who may not be aware of the existence of blue-eyed people.
posted by mr_roboto at 3:36 PM on February 15, 2008

omiewise, you're making everyone kill themselves several times over? doesn't make sense. also, why jane?

for real, I'm out now.
posted by shmegegge at 3:39 PM on February 15, 2008

oh my god you're right arrgh

i blame the president
posted by East Manitoba Regional Junior Kabaddi Champion '94 at 3:40 PM on February 15, 2008

oh my god you're right arrgh

i blame the president
posted by East Manitoba Regional Junior Kabaddi Champion '94 at 3:40 PM on February 15, 2008

Your reformulation is fine, but I still disagree with your conclusion.
Okay, we're repeating ourselves. If I understand you, you keep saying: for N=5, No one could believe that someone else believes that he is the only BEI. (Or numerical variations thereof)
I keep saying: You are right, but people could believe that other believe that other people believe the above statement.
Apparently you think that believing other people believe it isn't strong enough for any suicides?

Your current statement of the argument also seems to imply that no one will suicide at a lower n, either.
So do you accept that for n=4 (ABCD),
A believes n=3
A believes BCD believe n=2
A believes BCD believe (BC/BD/CD) believe n=1
And that therefore A expects BCD to suicide at t=3
At t=4 with no suicides, ABCD believe n=4 and suicide?

Because to me, this is identical to the case for n=5 but with one less recursion. Once again though, it's true that with no nnouncement, and n=4, everyone knows there are BEIs and everyone knows everyone knows there are BEIs, and I think one more iteration (don't feel like re-counting.) So there's no reason for anyone to suicide at t=1, t=2, or t=3.

On preview: crap.
posted by agentofselection at 3:41 PM on February 15, 2008

oh my god double post arrgh

In the unlikely event that this makes it clearer to people:

If the island has 3 blue-eyed people on it, A B and C...

As far as A knows, there might only be 2 blue-eyed people on the island...

A asks, what does B know? Imaginary B might be only able to see one person with blue-eyes.

And as far as IMAGINARY B knows, C might be the only person with blue eyes.

So DOUBLE-IMAGINARY C (the C imagined by the B imagined by A) might not know that ANYONE has blue eyes.

So when the traveller makes his proclamation in front of the crowd, it's new information.

Now, [(Everyone knows that) x infinity] there is at least one islander with blue eyes.

So the COUNTDOWN TO DESCTRUCTION BEGINS. And this pattern can be applied all the way up to 100 blue-eyes.
posted by East Manitoba Regional Junior Kabaddi Champion '94 at 3:47 PM on February 15, 2008

That's it, Champ!
posted by mr_roboto at 4:04 PM on February 15, 2008

They don't have to all kill themselves. A single blue-eyed individual can be sacrificed immediately sacrificed instead. This would break the induction.
posted by Flunkie at 4:36 PM on February 15, 2008

Yeah, or they could all become Lutherans.
posted by East Manitoba Regional Junior Kabaddi Champion '94 at 4:39 PM on February 15, 2008

The outsider's pronouncement doesn't add any information. Everyone already knew that there was at least one blue eyed person.

For some reason, the tribes people take the outsider's pronouncement as starting the suicide clock, and if you take that at as a given, the induction does indeed work.

However, there's nothing more "logical" about starting the suicide clock when the outsider makes his pronouncement than starting it at any other time.

The puzzle would make more sense if the suicide rule were enacted at a distinct time, after everyone had been able to memorize everyone else's eye color.
posted by Mr. President Dr. Steve Elvis America at 5:05 PM on February 15, 2008

Does someone have a really simple, plain English solution?

No complicated figures or technical terms or long-winded explanations, I mean.
posted by cmgonzalez at 5:18 PM on February 15, 2008

The outsider's pronouncement doesn't add any information. Everyone already knew that there was at least one blue eyed person.

This is true, but knowledge of the presence of at least one blue-eyed person is not sufficient for any of the blue-eyed people to determine they are blue-eyed.

Let's consider the simple case with three blue-eyed people. Each of these people must consider the possibility that they are brown-eyed. If this is the case, then there are only two blue-eyed people. Each of our blue-eyed observers (who is currently considering the possibility that they are brown-eyed) models the state of mind of the other two blue-eyed people as follows:

I can see exactly one blue-eyed person. I must consider the possibility that I am brown-eyed. If this is the case, the blue-eyed person I see is the only blue-eyed person on the island, and is unaware of this fact. That is, there is one blue-eyed person on this island, but that person is unaware that there is one blue-eyed person on this island. That's why no one is committing suicide.

So, in the group of three people, each person can entertain the possibility that they are brown-eyed with no logical contradictions. Similarly, they can entertain the possibility that they are blue-eyed (the argument works the same way). So they have no way to know what their eye color is.

Once the stranger comes, the logic in the small type breaks down. Each of the three blue-eyed people knows that they cannot be brown-eyed without a contradiction after 3 days. Hence, the suicide.
posted by mr_roboto at 5:27 PM on February 15, 2008 [1 favorite]

The outsider's pronouncement doesn't add any information. Everyone already knew that there was at least one blue eyed person.

Your problem is that you're assuming that these two statements are equivalent, when in fact they are not.
posted by Flunkie at 5:44 PM on February 15, 2008

It is awesome that this is post number 69105.
posted by inkyz at 5:48 PM on February 15, 2008

Does someone have a really simple, plain English solution?

Forget about 100 people. Let's say it's you and Cindy on this island, and Cindy's got blue eyes.

The stranger comes along, and says that someone has blue eyes.

You wake up the next morning, and Cindy has not killed herself.

What can you deduce from this fact, that you couldn't have deduced the day before?
posted by Flunkie at 6:12 PM on February 15, 2008 [2 favorites]

And now let's say it's you, Cindy, and Pete. Cindy and Pete have blue eyes.

The stranger comes along, and says that someone has blue eyes.

If you have brown eyes, then Cindy and Pete are essentially in the same situation as you and Cindy were in my last post. So, they'll kill themselves in two days, just like you and Cindy would have in my last post.

But two days pass, and Cindy and Pete are still alive and kicking.

What can you deduce from this fact, that you couldn't have deduced the day before?
posted by Flunkie at 6:15 PM on February 15, 2008

Your problem is that you're assuming that these two statements are equivalent, when in fact they are not.

That's true, but everyone already know that everyone knew there was at least one blue eyed person.

What they needed was an agreed upon time to start the inductive process. Everyone had to be sure everyone was counting from the same moment. I don't see how the traveler's statement can be fairly seen as fixing that moment to a logical certainty.
posted by Mr. President Dr. Steve Elvis America at 6:17 PM on February 15, 2008

I'm sorry, all this discussion is reminding me of Vizzini debating Westley while trying to decide which cup holds the poison.

But it's so simple. All I have to do is divine from what I know of you: are you the sort of man who would put a blue-eyed man into his own path or his enemy's? Now, a clever man would put a blue-eyed man into his own path, because he would know that only a great fool would reach for what he was given. I am not a great fool, so I can clearly not gouge out the eyes of the man in front of you. But you must have known I was not a great fool, you would have counted on it, so I can clearly not gouge out the eyes of the man in front of me.

It's like the Pants game, but more squicky and twisted!
posted by Reth_Eldirood at 6:17 PM on February 15, 2008 [1 favorite]

Andy now it's you, Cindy, Pete, and Brenda. Cindy, Pete and Brenda have blue eyes.

The stranger comes along, and says that someone has blue eyes.

If you have brown eyes, then Cindy, Pete and Brenda are in essentially the same situation as you, Cindy, and Pete were in my last post. So, they'll kill themselves in three days, just like you, Cindy and Pete would have in my last post.

But three days pass, and Cindy, Pete and Brenda are still here.

What can you deduce from this fact, that you couldn't have deduced the day before?
posted by Flunkie at 6:17 PM on February 15, 2008

Repeat ad nauseum.
posted by Flunkie at 6:17 PM on February 15, 2008

That's true, but everyone already know that everyone knew there was at least one blue eyed person.

What they needed was an agreed upon time to start the inductive process.

That's not correct. It really has nothing to do with the issue.

Yes, everyone knew there was at least one blue eyed person. In fact, everyone knew there were at least 99 blue eyed people.

But nobody knew that everybody knew that everybody knew that everybody knew that everybody knew that everybody knew that ... that everybody knew that there was at least one blue eyed person.

Now they do.

That's the information that the stranger added. And it's fatal.

"A time to start the inductive process" is just handwaving.
posted by Flunkie at 6:20 PM on February 15, 2008

That's true, but everyone already know that everyone knew there was at least one blue eyed person.

Not so.

Consider the simple case of two blue-eyed people. Everyone on the island knows that there is at least one blue-eyed person. However, each blue-eyed person knows there is either one or two blue-eyed people. If there is only one, that one does not know that there is at least one blue eyed person on the island.

So everyone knows, but there are two people who can't be sure that everyone knows that everyone knows.
posted by mr_roboto at 6:24 PM on February 15, 2008

Sorry; of course the same thing applies to the brown-eyed people, so every person cannot be sure that everybody knows that everybody knows.
posted by mr_roboto at 6:29 PM on February 15, 2008

Dr Steve: Everyone knows that there are blue eyed people on the island, but everyone knows that no one else knows that they themselves have blue eyes.

Say there are 10 people on the island, and 2 of them have blue eyes. You are one of those two people.

8 people on the island know two things and don't know 1 thing:

At least two people have blue eyes,
Those 2 people don't know that they have blue eyes (or they'd have killed themselves already)

They don't know if they themselves have blue eyes.


2 people on the island know 2 things and don't know 1 thing.
At least one person has blue eyes.
That person does not know he has blue eyes or they would have killed themselves.

They don't know if they themselves has blue eyes.

So, when someone comes on the island and says "Someone has blue eyes," what's changed.

Now everybody knows that everybody else knows that someone on the island has blue eyes.

If you're one of the 8 people with brown eyes you know the following on day 1.

1. Neither of the blue eyed people will kill themselves because they still don't know if they have blue eyes or not.

They still do not know if they themselves have blue eyes.

On day 1, the two blue eyed people know this:

1. If the only blue eyed person that they know of doesn't see any other blue eyed people, then he himself knows that he must have blue eyes, then he'll kill himself
2. They don't know themselves if they have blue eyes or not.

After Day 2.

The two blue eyed people know that since the other person did not kill themselves last night that they must have seen another blue eyed person. Since they don't see any, then they must BOTH know that they have blue eyes and will kill themselves that night.

What changed by the stranger telling people that there were blue eyed people on the island was that everyone knew that everyone else knew there were blue eyed people on the island.

-

A stand-up comic said -- My mom told me there's an idiot on every bus. I know that's wrong, because I was on a bus the other day, and I didn't see any idiots.
-
Same basic idea.
posted by empath at 6:32 PM on February 15, 2008

But nobody knew that everybody knew that everybody knew that everybody knew that everybody knew that everybody knew that ... that everybody knew that there was at least one blue eyed person.

Of course they did. Everyone has seen that everyone will be able to see other people seeing blue eyed people. They know that everyone will draw the appropriate inferences.

So everyone knows, but there are two people who can't be sure that everyone knows that everyone knows.

Your serious suggestion is that on an island with 100 blue eyed people milling about, there's going to be doubts about the general awareness of the presence blue eyed people?
posted by Mr. President Dr. Steve Elvis America at 6:33 PM on February 15, 2008

Of course they did.

No, they didn't.

Let's say you - you - are on such an island. There are a bunch of people, but only two that you know of - Edna and Luanne - have blue eyes.

You know that there's at least one person with blue eyes.

And you know that Luanne knows there's at least one person with blue eyes.

And you know that Edna knows there's at least one person with blue eyes.

None of that is in question.

What you seem to be missing here is that you don't know that Edna knows that Luanne knows that there's at least one person with blue eyes.

That is, you don't know that everyone knows that everyone knows that there's at least one person with blue eyes.

So not everyone knows that everyone knows that everyone knows that there's at least one person with blue eyes.

The stranger's statement changes that.

If you still disagree, please explain to me exactly, step by step, how you know that Edna knows that Luanne knows that there's at least one person with blue eyes.
posted by Flunkie at 6:42 PM on February 15, 2008

What you seem to be missing here is that there are 100 blue eyed people on this island.
posted by Mr. President Dr. Steve Elvis America at 6:44 PM on February 15, 2008

Your serious suggestion is that on an island with 100 blue eyed people milling about, there's going to be doubts about the general awareness of the presence blue eyed people?

Let's put it this way.

You're one of those 100 blue eyed people. You see 99 blue-eyed people. If you consider the possibility that you're brown-eyed, then those 99 blue-eyed people are behaving as if there are only 99 blue-eyed people on the island. Each one of them must consider the possibility that they are brown-eyed, and that the other 98 blue-eyed people are behaving as if there are 98 blue-eyed people on the island. Each on of them must consider the possibility that they are brown-eyed, and that the other 97 blue-eyed people are behaving as if there are 97 blue-eyed people on the island.... All the way down to two people, where it reduces to the simple case where each blue-eyed person knows there is either one or two blue-eyed people. If there is only one, that one does not know that there is at least one blue eyed person on the island.

So long as it has not been made common knowledge that there is at least one blue-eyed person on the island, this chain of reasoning prevents any person from determining their eye color.
posted by mr_roboto at 6:46 PM on February 15, 2008 [1 favorite]

Ugh.

Explain to me, step by step, how you know that Edna knows that Luanne knows that Frank knows that June knows that Daisy knows that Pete knows that ... that Joe knows that there's at least one person with blue eyes.
posted by Flunkie at 6:46 PM on February 15, 2008

I'll grant you, it's a nonintuitive conclusion. But I'm pretty sure it's ironclad.
posted by mr_roboto at 6:47 PM on February 15, 2008

Each on of them must consider the possibility that they are brown-eyed, and that the other 97 blue-eyed people are behaving as if there are 97 blue-eyed people on the island

But everyone knows that nobody thinks there are 97 blue eyed people on the island.
posted by Mr. President Dr. Steve Elvis America at 6:47 PM on February 15, 2008

Right.

So at each step of the process I outlined above, there are of course 100 blue eyed people on the island. But in the first step, one of those person has made an assumption that there are 99 blue-eyed people on the island, and now needs to work out the logical implications of that assumption. He's looking at each of those 99 people, and considering what their mental state is. Of course, it's possible that they think that there are only 98 blue-eyed people on the island.

Now, notice that the initial assumption is wrong. There are not 99 blue-eyed people on the island. However, based on the information the first person has, he cannot know that this assumption is wrong. When considering the other 99 people, he knows that they can make the incorrect assumption that there are 98 people and, because of their lack of information, encounter no logical contradictions.

So at every step of this process, an incorrect assumption is made. And the person imagining the mental state of the other islanders knows that this assumption is incorrect, but he also knows that there is nothing to inform the person making this assumption of its incorrectness.
posted by mr_roboto at 7:00 PM on February 15, 2008

OK, if they only kill themselves the next day if they KNOW their own eye color, then no one dies.

A visitor mentioning that someone has blue eyes does not knowledge make.

You would need another devout and logical villager to tell you directly, then and only then will you "know".

The puzzle would have been better if this was clarified, and if the whole 2 eye colors and no more aspect was clarified.
posted by parallax7d at 7:15 PM on February 15, 2008

Dude, you've just gotta buy the premises, alright?

Do you argue about how the chess pieces move?
posted by mr_roboto at 7:16 PM on February 15, 2008 [1 favorite]

OK, if they only kill themselves the next day if they KNOW their own eye color, then no one dies.

Well, no. You're right that the browns do not die, using the phrasing of the question in this post, since, as you point out, they still don't know if they've got brown eyes; all they know is they don't have blue eyes.

But the blues know they're blue. They still die.
posted by Flunkie at 7:19 PM on February 15, 2008

Oh, maybe I misread what you were saying, parallax7d. If you were saying that this post doesn't explain that they have a reason to believe the stranger, then yeah, you're right, no one dies.

But this is a famous puzzle; the way it was phrased in this post isn't its canonical form (wherein it's a base assumption that the stranger is trusted).
posted by Flunkie at 7:25 PM on February 15, 2008

In fact, the link does give exactly that as a base assumption: the stranger "wins the complete trust of the tribe."
posted by Flunkie at 7:27 PM on February 15, 2008

As someone who has studied computer science for most of his adult life, I got the question and the solution pretty quickly. I appreciate a solution that requires knowledge of both induction and the pigeonhole principle.

This is a delightful problem for a couple reasons. Suppose I'm an islander. The real question behind all of it is, given fact X (some of us are blue eyed), and goal Y (kill myself if I find out that I am blue-eyed), is there an algorithm Z which, if all the islanders follow it, allows us to reach goal Y? Of course, it's wonderfully subversive that the goal is to kill oneself. But the other underlying assumption is that given an algorithm which is proven to work, each islander will execute it faithfully.

The algorithm that's been given as a solution, of course, is to agree that you will count the number of people you see who have blue eyes, call it K, and wait for K days. If on that day all the blue-eyed people kill themselves, and you aren't one of them, then you know you don't have blue eyes. If, on the other hand, this mass suicide doesn't happen, then you know that you too have blue eyes, and you must kill yourself on day K+1. Hopefully it's clear (at least it's clear to me) that if everyone follows that algorithm in good faith, it will take care of all the blue-eyed people in a societally acceptable way.

I hope I've explained why I, from a computer science perspective, found this problem interesting. I don't really have a response for the people who objected to the premises of it. Either you treat it as a logic problem, or you think it's stupid. Best if you decide which you prefer quickly, and leave us logic lovers in peace, or join us.
posted by A dead Quaker at 7:55 PM on February 15, 2008 [3 favorites]

I'm not arguing here - if this is a classic puzzle then obviously I'm the one who's wrong. I've read the whole thread and I don't get why anyone has to die when there are 99 blue eyed people. Or FOUR. Given that everyone can see everyone else's eyes.
So if A is the only one with blue eyes, he realizes it's him and has to kill himself.
If A and B are the only ones, no death day one, they realize both of them have to kill themselves.
If A and B and C are the only ones, then C EXPECTS A & B to off themselves day two because C believes the A and B each only see ONE other blue eyed person. When they don't, C knows she's got them too.
But why doesn't the chain stop at four?
A B C & D have blue eyes. They EACH see three people with blue eyes. So why doesn't everyone just think, "no shit, yeah, some people have blue eyes". With four, why would anyone have a reason to conclude anything about their own eye color?
posted by moxiedoll at 8:06 PM on February 15, 2008

Because the fourth person is assuming that the three people he sees will operate as if they are the only three people with blue eyes. (And you've already established why and how three people would end up killing themselves.) If they don't, then the fourth knows he has blue eyes.
posted by OmieWise at 8:16 PM on February 15, 2008

moxiedoll.... for the same reason as three. :/
If the three people don't kill themselves on the third day, and EVERYONE ELSE on the island has brown eyes, and day four dawns, well... time to go for bluey number four.

Here, I'll stage it:

Day Three
Internal Monologue

Bluey #4: Well, it's day three and no deaths. Bob, Hank and Jessie all have blue eyes, damn them to hell, but they haven't killed themselves. Hopefully they do it tonight.

Day Four dawns.

Bluey #4: Shit. Bob, Hank and Jessie all have blue eyes, and haven't killed themselves. And absolutely everyone else on this island has brown eyes. The only person I can't confirm is myself, and since the other three aren't dead that means that I have blue eyes.
posted by Baby_Balrog at 8:41 PM on February 15, 2008

Ok, your right Flunkie. I was thinking "trust does not truth make" but then I realized that if they trusted him, they would assume he was telling the truth, therefore assuming he was correct. It's their own fault for trusting him, since as a wise man knows, trust does not truth make.

On the other hand, even if a villagers trusted the man, they still wouldn't know how many eye colors were on the island, and therefor could never infer what their own eye color was. They could assume that their own eyes were either blue or brown (an illogical assumption) but they could indeed be green.

Any way, if you break it down into 4 people it seems easy to solve.

4 villagers, green, blue, blue, brown.

day 1: they all notice that the other villager(s) with blue eyes don't kill themselves

day 2: nothing happens, since they still don't know what their own eye color is. they cant assume it's blue based on the comment. move along...


Now if there were only 2 villagers, both with blue eyes it makes even more sense.

day 1: they each notice the other failed to kill themself
day 2: nothing happens, since they know they can't infer their own eye color simply based on the lack of knowledge the other person has about their own eye color. Simply not enough info.


Now if there was 1 villager, that's simple.

day 1: villager kills themself.


Their simply isn't enough info provided to the villagers. If the visitor said "there are only two eye colors on the island, and I am surprised to see blue" then that would be enough info for the mass suicide to happen.
posted by parallax7d at 9:30 PM on February 15, 2008

this problem, and others like it, neatly divides homo sapiens into 3 sub-species.

the Understanders
the Insisters
the Deniers

there are many social metrics on which the stratification of these three sub-species are evident, but with (the discussion of) logic puzzles the stratification is by far the most pronounced.

Some other metrics:

Intelligence, from high to low: Understanders, Insisters, Deniers

Success/wealth, from high to low: Insisters, Understanders, Deniers

Happiness, from high to low: Deniers, Understanders, Insisters

Sexual attractiveness, high to low: Insisters, Deniers, Understanders

Physical ability, high to low: Deniers, Insisters, Understanders


For any understanders: this problem is quite trivial to understand if you forget all about 100 blue-eyeds & imagine 3 blue-eyed people. That advice, however, is useless to a Denier or an Insister. Even if an Insister is capable of working out the 3-person solution in their head, they will insist that 100 people is different for some reason they are never quite able to precisely elucidate but are quite confident exists.
posted by lastobelus at 9:40 PM on February 15, 2008 [1 favorite]

oh, and in case it isn't obvious: Insisters rule the world. In no small part because Deniers, who are the largest group by a substantial amount, perversely tend to believe and trust Insisters over Understanders.
posted by lastobelus at 9:46 PM on February 15, 2008 [1 favorite]

Understanders will tend to ignore or gloss over any deficiencies in how the premises are stated, or just mentally fix them so they can get to the problem. Because the principle illustrated by the problem is interesting in a fundamental way.

Insisters will focus on the premises because they are far more motivated by finding a way to cheat the premises than they are by understanding them.
Also Insisters pick at the premises to find ways to justify why the answer they've already decided on is "right" when Understanders point out that it is not in fact right.

Some Understanders will pick at the premises, not because they want to arrive at a different conclusion, but because they want to make the problem as "pure" as possible.

Deniers pick at the premises primarily to to find ways to substantiate the idea that the principle the problem embodies is unimportant, unconnected to reality, fundamentally flawed etc. -- i.e., to find ways to justify why it is NOT WORTH understanding.
posted by lastobelus at 10:03 PM on February 15, 2008 [1 favorite]

There is at least one Insister in this thread.


(well hey, it was worth a shot)
posted by lastobelus at 10:04 PM on February 15, 2008 [1 favorite]

B might believe that C might believe that D might believe that there are no blue eyed people on the island.


No, if there are 99-100 BEI, nobody thinks that anybody thinks that there are no BEI. Everyone knows there are plenty of BEI.

Full disclosure, I have blue eyes
posted by jpdoane at 10:04 PM on February 15, 2008

I missed this part, or maybe it was added after the first time I read it:

[Added, Feb 15: for the purposes of this logic puzzle, “highly logical” means that any conclusion that can logically deduced from the information and observations available to an islander, will automatically be known to that islander.]

Okay, now I understand that they kill themselves. The question makes a lot more sense in smaller numbers because one doesn't have to make up highly specific definitions of "highly logical" to explain how everyone on the island memorized everyone else's eye color.
posted by Bookhouse at 10:16 PM on February 15, 2008

It may have been articulated this way up above already, but I skipped half of the comments...

To understand how the induction argument works you have to understand the case where there are 2 blues and 998 browns. The blues know, based upon what they can see, that there either have to be 1 blue or 2 blues. The browns know that there either have to be 2 blues or 3 blues. On the first day no one kills themselves because they see at least one other blue.

On the second day when they wake up and find that no one has committed suicide, that tells everyone that there cannot have been exactly 1 blue on the island. For the browns, who think there have to either be 2 or 3 blues, it's not conclusive yet - they're still not absolutely sure what their own eye color is.

But for the blues, who know there has to be exactly 1 or 2 blues on the island, it's conclusive: there can't have been just 1 blue, so there are 2 - one they can see in the rest of the population and one they can't - so each of them now knows they have blue eyes. So they both commit suicide.

On the third day everyone else on the island wakes up and finds that 2 people have killed themselves. All the people left alive thought there either had to be 2 or 3 blues on the island, so deductively they can now conclude that there were 2 and they themselves do not have blue eyes.

Similarly, if there were 3 blues, then they'd wake up on the third day finding no bodies and could be certain that there wasn't exactly 1 blue and there weren't exactly 2 blues, so they'd kill themselves (because they're each sure they're one of 3 blues - 2 they can see and themselves). Whereas all the browns, who didn't commit suicide because they thought there could've been 4 blues, wake up on the fourth day and find three bodies and know their eyes aren't blue.

So you can see that it extends up to any number of blues in this fashion.

On the day after they see that the blues killed themselves, if there's some way to know that the entire population has either blue or brown eyes, the browns will all kill themselves. If they think there could be at least a third eye color they live.

The islanders also have to know how many blue-eyed blind (and colorblind) people there are on the island and take account of that when they're counting bodies. “Why did only 99 people kill themselves even though yesterday was day 100?” Talk about an uncomfortable situation.
posted by XMLicious at 10:41 PM on February 15, 2008

define logic.
posted by SageLeVoid at 1:01 AM on February 16, 2008

what would Davis Bowie do?
posted by the_very_hungry_caterpillar at 1:25 AM on February 16, 2008

David, even!
posted by the_very_hungry_caterpillar at 1:25 AM on February 16, 2008

If one factors in uncertainty within Theory of Mind of others, then it's much more unclear.

For n = 5

1 sees 2, 3, 4, 5
1 thinks there are atleast 4 and upto 5

1 believes 2 to see 3, 4, 5 and maybe 1
1 believes 2 to think either there are atleast 3(3,4,5) or 4(3,4,5,1 OR 3,4,5,2) and maybe 5(3,4,5,1,2)

1 believes 2 to believe that 3 sees 4, 5 and maybe 1, 2
1 believes 2 to believe that 3 either thinks there are 2(4,5) or 3(4,5,3) or 4(4,5,1,2) or 5(4,5,1,2,3)

1 believes 2 to believe 3 to believe that 4 sees 5 and maybe 1, 2, 3
1 believes 2 to believe 3 to believe 4 to believe either there is 1(5) or 2(5,4 OR 5,3 OR 5,2 OR 5,1) or ... screw it. No one's committing suicide in this model.
posted by Gyan at 2:02 AM on February 16, 2008

Gyan, I don't get what you're saying, it's all pretty certain - for each person there are only two possibilities:

• β, the number of blues is exactly the number of blue-eyed people she sees
• β+1, the number of blues is the number seen plus one, herself

And as far as worrying about what anyone else thinks the only question is “do I have blue eyes” which everyone else will agree upon and will be revealed by whether or not anyone kills themselves on day β.

The facts are almost entirely established and the small uncertainties will be revealed on day β-1 or day β (depending on whether your eyes are blue or brown), that's the point. All they have to do is wait and see.
posted by XMLicious at 2:39 AM on February 16, 2008

Yes, the ultimate question is "Do I have blue eyes?" but the answer is not presented and has to be deduced by the person himself. So, there's an implicit model of behavior of other agents adopted by the subject i.e. Theory of Mind, to interpret actions of others.

Our initial subject starts by acknowledging that they don't know their own eye-color i.e. there's uncertainty. They ought to allow for the same factor when simulating nested others' thoughts recursively. That uncertainty permeates at all levels of nesting and the permutations of possible thoughts increase with each level. I'm not saying for sure that no one will or will not commit suicide but that it's no longer that straightforward. If there's no uncertainty accommodated when simulating others' thoughts, then the solution is tedious but unambiguous.
posted by Gyan at 3:00 AM on February 16, 2008

But if they know that the question “Do I have blue eyes?” is going to be answered at a specific time why would they bother trying to simulate other people's thoughts in the first place?

And even if a particular person did try to simulate everyone else's thoughts, everyone else's thoughts are identical to his own except that their values for β might be one more or one less.

I think you might be trying to treat this as some kind of psychological question, but it isn't. Or, wait, by “Theory of Mind” do you actually mean “Game Theory”? That doesn't apply here either. Not only are they not competing - they want to die if they have blue eyes - but there's only one optimal course of action and it's the same for all players.
posted by XMLicious at 3:39 AM on February 16, 2008

But if they know that the question “Do I have blue eyes?” is going to be answered at a specific time

But it's not going to be answered at any time. No one's telling the first person that she has blue eyes. She is modelling the thoughts of other persons to predict their behavior and then observing the outcome to generate inferences. The notion that the time-series of suicides is indicative of so & so is not an axiom but a theorem borne of first principles related to Theory of Mind modeling i.e. if person X knows that they have blue eyes, then they will commit suicide.
posted by Gyan at 4:59 AM on February 16, 2008

All the 'lateral' 'thinkers' in this thread remind me of a 7 year old boy disputing a lost chess game by arguing that the king would in fact be able to move at least as far as the queen.
If you can't understand or play the game, disputing the rules won't make you seem clever. Just whiny.
posted by signal at 5:06 AM on February 16, 2008

Their simply isn't enough info provided to the villagers. If the visitor said "there are only two eye colors on the island, and I am surprised to see blue" then that would be enough info for the mass suicide to happen.

No, it's not necessary that there only be two eye colors. If there's 100 people with blue eyes, 700 with brown eyes, 100 with hazel eyes, 90 with green eyes, and 10 red-eyed albinos, the BEIs still kill themselves on day 100.

Consider the 2-BEI case. After the islander's pronouncement, A says to himself, "only B has blue eyes, as far as I know. If B doesn't see anyone else with blue eyes, he'll kill himself at noon, because he'll know he must have blue eyes. He may see brown and green and hazel and red and pink and white and plaid and polka-dotted eyes, but as long as he sees no other blue eyes, he'll know his eyes must be blue."

Noon, comes around, and B does not kill himself. Now A says, "Since B didn't kill himself, he must see someone else with blue eyes. I don't see anyone other than B with blue eyes--even though I do see people with brown, blue, hazel, green, purple, yellow, and fuschia eyes--so the person with blue eyes that B sees must be me. Well, shit."
posted by DevilsAdvocate at 5:29 AM on February 16, 2008

Your serious suggestion is that on an island with 100 blue eyed people milling about, there's going to be doubts about the general awareness of the presence blue eyed people?

No, the suggestion is that with 100 blue-eyed people, there will be doubts about the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the general awareness of the presence of blue-eyed people, until the visitor makes his pronouncement.
posted by DevilsAdvocate at 5:34 AM on February 16, 2008 [1 favorite]

Noon comes around, and B does not kill himself. Now A says, "Since B didn't kill himself, he must see someone else with blue eyes. I don't see anyone other than B with blue eyes--even though I do see people with brown, blue, hazel, green, purple, yellow, and fuschia eyes--so the person with blue eyes that B sees must be me. Well, shit."

Fixed that for myself.
posted by DevilsAdvocate at 5:37 AM on February 16, 2008

If you can't understand or play the game

Hmm, that might be another key as why some people have trouble with this. Many people at least have some exposure to chess, but how many have had exposure to logic puzzles and their rules?

Chess makes perfect sense to me in that I learned it when I was young and *know* how each piece is supposed to move. There's zero questioning of why the king can't move as well as the queen because it just *is* and to even argue about it is just silly.

It also might help us slow people if logic puzzles were framed as games, which everyone understands to have certain rules as opposed to framed as story involving people.
posted by Brandon Blatcher at 5:39 AM on February 16, 2008

The eye problem seems to be different from the bbq problem in that in the second problem the chef rings the bell as long as there are messy faces left. This allows the diners to know when all messy faces have been cleaned. In the blue eye problem, I don't see how one can conclude that all blue eyed indidivuals are dead.
posted by humanfont at 6:05 AM on February 16, 2008

parallax7d:

Any way, if you break it down into 4 people it seems easy to solve.

4 villagers, green, blue, blue, brown.

day 1: they all notice that the other villager(s) with blue eyes don't kill themselves

day 2: nothing happens, since they still don't know what their own eye color is. they cant assume it's blue based on the comment. move along...

No, sorry, you're still wrong. They're not "assuming", they're deducing.

Forget about it being four abstract people. Think about it as three abstract people and you.

All your life, you've seen these three other people. Emma has green eyes. Audrey blue. Ellen brown. You have no idea what your own eye color is.

Somebody comes along and says that someone has blue eyes.

Audrey has blue eyes. But she doesn't kill herself.

That means that she already knew someone had blue eyes. Because otherwise, she would have easily and correctly concluded that she has blue eyes, and therefore killed herself.

So, Audrey already knew someone had blue eyes. Who?

Audrey didn't know Emma has blue eyes. Emma doesn't have blue eyes.

Audrey didn't know Ellen has blue eyes. Ellen doesn't have blue eyes.

Audrey didn't know she herself had blue eyes. She's never seen her eyes.

But Audrey knew somebody had blue eyes. And there's only one person left who that could possibly be.

Who? Who's that other person with blue eyes?
posted by Flunkie at 6:18 AM on February 16, 2008

On the 100th day, the blue-eyed meet up, decide that the whole suicide thing is stupid, and just get drunk.

On the 101st day, the servantile brown-eyed kill themselves.

102nd onwards - The blue-eyed inherit the earth.
posted by spongeboy at 6:58 AM on February 16, 2008

So, am I correct in thinking that every single brown-eyed person has plans to kill themselves on day 101 that they are able to call off because of the mass suicides on day 100?
posted by Bookhouse at 7:05 AM on February 16, 2008

So, am I correct in thinking that every single brown-eyed person has plans to kill themselves on day 101 that they are able to call off because of the mass suicides on day 100?

If they know that everybody either has brown eyes or blue eyes.

But if they don't, then any one of them can only conclude "the island had exactly 100 blue eyed people, 899 brown eyed people, and me. I might have brown eyes - in fact I probably have brown eyes, but for all I know, my eyes might be neon pink."
posted by Flunkie at 7:11 AM on February 16, 2008

Wait, I misread your question. Yes, they each had a plan to kill themselves on day 101 if there was no mass suicide on day 100. And yes, they call it off, because the mass suicide on day 100 means they can't conclude their own eye color. They can conclude it's not blue, but they can't conclude what it actually is.
posted by Flunkie at 7:14 AM on February 16, 2008

I didn't get it at first - mostly because I was missing the concept of an iteration (noon in the town square). Would it work if there was no such ritual? Either way, I enjoy the image of the islanders nervously shifting their weight from one foot to the other in the town square on day 99. Thanks to everyone who took the time to explain it.

(And I am still sympathetic to the argument that they'd all kill themselves on day 1 on the knowledge that they would all eventually conclude their eyedness.)
posted by These Premises Are Alarmed at 7:54 AM on February 16, 2008

(oh damn shoulda previewed! wow.)
posted by These Premises Are Alarmed at 7:55 AM on February 16, 2008

I spent a bus ride yesterday trying to think up a clearer way to explain the chain of induction here, the way that the villagers' recursing reasoning leads, one clear step at a time, up to the mass suicide. I haven't really gotten my method down—several folks have made game attempts upthread to do the same thing, and I'm not sure what I could do to improve their efforts—but I have a feeling I'll be thinking about it for a while.

One thing that stands out to me, though, is how different people here are using words like "believe" vs. "assume" in talking about how these folks* go about reckoning one another's expectations about eye color. The inductive reasoning depends on being able to move through a series of models of the situation where n-1, n-2, n-3 people are assumed to have blue eyes, and it's that assumption that's key.

Nobody on the island ever believes that there are a mere handful of blue-eyes, or a single blue-eye; you're right to say, "that doesn't make sense, how could they believe that, there's dozens of them." And the thing is, in no part of the inductive reasoning is "villager x believes he does/doesn't have blue eyes, and so thinks villager y does or doesn't..."

Each villager just posits an assumption. They take an unknown, and they plug in a presumption: "I don't know my eye color, so I'll assume as a hypothetical that my eyes are not blue; and given that assumption, I'll reason in my mind what the folks I know to have blue eyes are thinking to themselves." The villager has not decided they aren't blue-eyed, they don't believe it; they know full well that they're in the dark on that. But the posit an assumption, and reason from there.

And that chains on down, a step at a time, to the logical conclusion of a single hypothetical assumer-of-nonblue-eyes realizing that their assumption is bunk: they've assumed that their eyes aren't blue, and yet they know as a GIVEN that someone's eyes must be blue, and that their eyes are the only unknown and so must be blue. Contradiction. Their assumption is proven wrong, and that chains back up, each hypothetical villager seeing his assumption disproven by contradiction all the way back to the initial assumption. And it's that horrible moment when all 100 blue-eyes realize that they've disproven their initial assumption, "I do not have blue-eyes", and so the opposite is true: "I have blue eyes." That's the moment of knowledge—before that, they believed nothing, had only assumed and tested, day-by-day, the validity or invalidity of their assumption.

Which, having typed that out, still doesn't seem like much help. Back to the drawing board.

^*(I keep wanting to call them Villagers, not Islanders; what color are Number 6's eyes?)

Chess makes perfect sense to me in that I learned it when I was young and *know* how each piece is supposed to move. There's zero questioning of why the king can't move as well as the queen because it just *is* and to even argue about it is just silly.

One of the few times I played chess with one of my sisters growing up (neither of us were regular players), I pulled an en passant on her and she accused me of making shit up and quit on me. Which was kind of understandable, because it's like, what? You get to capture my pawn by moving to a space where it isn't? What the fuck, man?

Which the comparison of chess to logic puzzles reminded me of. Because there's this sort of undeclared set of rules—induction, proof by contradiction, etc—that not everybody walks into the door with. They're all there, documented, available for deployment if you want to study up, but anybody can sit down with a word problem and have a go at it and so part of these arguments is a disagreement not just about the premise of the problem but about the rules you're allowed to play by in finding a solution.
posted by cortex at 9:06 AM on February 16, 2008 [1 favorite]

cortex: Each villager just posits an assumption. They take an unknown, and they plug in a presumption: "I don't know my eye color, so I'll assume as a hypothetical that my eyes are not blue; and given that assumption, I'll reason in my mind what the folks I know to have blue eyes are thinking to themselves."

Assigning this assumption unto the subject's thinking is a choice by the problem-solver and isn't implicit within the problem statement. What happens if one decides to accommodate the uncertainty within their thinking?
posted by Gyan at 9:19 AM on February 16, 2008

cortex wrote...
Because there's this sort of undeclared set of rules—induction [...]

Induction has been so badly abused in this thread that it may never walk again.
posted by tkolar at 9:48 AM on February 16, 2008

I was missing the concept of an iteration (noon in the town square). Would it work if there was no such ritual?

Maybe, maybe not. If they simply have to kill themselves as soon as they know their eye color, it would work something like this:

If there's just one BEI, he figures out pretty much right away, after the visitor's announcement, that he's the BEI and must kill himself.

If there's two BEIs, there's a bit of a pause. After a while, A starts thinking to himself, why hasn't B killed himself yet? Because if B were the only BEI, he'd have killed himself pretty much right away...OMG, I must have blue eyes too! And A and B kill themselves.

If there's three BEIs, there's an even longer pause. Eventually A might say to himself, B and C should have worked out by now they're the only two BEIs (by the logic in the previous paragraph). But they haven't! Why not? It can only be because they each see two other BEIs...so I must be blue-eyed too!

If there's a hundred BEIs, you start getting into questions about how much each person knows about how quickly the other people reason and how quickly they react. Would there be a point at which a BEI can say to himself, "If there were only 99 BEIs, they would have figured that out by now..."? I don't know. The point of the ritual suicide at noon is to avoid such objections.

Another twist: if just one of the BEIs is deaf, and thus can't hear the visitor's announcement (and everyone knows he's deaf), the entire chain of induction fails and no one has to die.
posted by DevilsAdvocate at 10:02 AM on February 16, 2008

the entire chain of induction reasoning fails and no one has to die.

Point taken, tkolar - fixed that for myself.

----

Assigning this assumption unto the subject's thinking is a choice by the problem-solver

The assumption isn't necessary. It's a helpful way of thinking about the issue, but the logic is the same regardless of whether the islanders assume they're brown-eyed or not, because the point is that such an assumption is eventually refuted anyway, for the BEIs. It doesn't make a difference whether a BEI assumes he's non-blue-eyed (which is refuted on day 100), or makes no assumption at all about his eye color (and discovers he's blue-eyed on day 100)
posted by DevilsAdvocate at 10:07 AM on February 16, 2008

Ed Norton voiceover: If you can't spot the sucker in the first half an hour at the table, then you are the sucker.
posted by rokusan at 10:17 AM on February 16, 2008

I'm not denying or insisting, I don't get something and I've been thinking stupidly about this all day. I know that I'm wrong but I don't get why. Maybe I'm not tiresome and someone wants to answer this specific question? OK. Yesterday I said that no one had to die with four and that was retarded of me. I get that if one, he kills himself day one, if two - both die day two, if three - all die day three. And that since each person in the blue eye set thinks there's one FEWER than the set, and believes that each person in their n-1 set believes that there's n-2 in the set, then if you start with five, you still wind up with each person assuming that everyone else thinks there's three. and so the deaths begin because everyone's surprised at the lack of day three death.
But I can't work it out if you start with *six*. Because you have to work backwards to get the problem to work (starting with 99) and I figure with 6, each of the six thinks there's 5, and each of the six thinks that those 5 poor bastards think there's only 4. Ok. If from anyone's wrong perspective the minimum number is four, why does the death watch start? If each of the six thinks that those other five believe there are four - you stop counting down. Nobody thinks that anyone thinks there are three or two or one. Why does anyone think that anyone would start offing themselves at all?
posted by moxiedoll at 12:58 PM on February 16, 2008

each of the six thinks that those 5 poor bastards think there's only 4.

Why? Each of those six blue-eyed people see five other blue-eyed people. Each non-blue-eyed person sees six blue-eyed people. Why would anyone think there were four?
posted by turaho at 2:32 PM on February 16, 2008

If there are six blue eyed people - say I'm one of them. I don't know about myself, so I think there are five. But I figure that since each of them can't see themselves, then each of them thinks there are four. I'm wrong, though - they can see five sets, same as me, and we're all ignorant about ourselves. So if I'm one of six, then I think there are five, and I think *they* think there are four.
posted by moxiedoll at 2:39 PM on February 16, 2008

Why would anyone think there were four?

No one thinks there are four. But if there are six blue-eyed people, each of them considers it possible that they are themselves brown-eyed, and that there are only five BEI--the five that they see. If it were the case that there were five BEI, then each of the five would only see four (since they don't know that they themselves are blue-eyed.) So each of the six BEI holds it as possible that they are non-blue-eyed, in which case there would be five BEI, all hoping that there are really just four.

So no one thinks there are four. But each of them thinks it is possible that every other BEI thinks there are four, since none of them know the truth--there are six BEI.

Since they are logical, they also know that the other possibility (which is the true one) is that there are six BEI--the five they see and themselves. But since being confirmed as a blue-eye means death, they hope, hope, hope that there are five who hope there are four.
posted by Pater Aletheias at 2:45 PM on February 16, 2008

Okay, I see what you're saying, but I think you're overcomplicating it. Each member of the island doesn't need to figure out what everybody is thinking. They just have to see if each blue eyed person they see behaves as logically expected as more and more information is revealed. Everybody should sit back, say "I see n number of blue-eyed people and logic says that n blue-eyed people will kill themselves on n day." And eventually that day will come for all the blue-eyed people and no one will kill themselves and simultaneously all the blue-eyed people will realize that's must mean there's one more blue-eyed person than they they thought and that person must be them.
posted by turaho at 3:05 PM on February 16, 2008

"I see n number of blue-eyed people and logic says that n blue-eyed people will kill themselves on n day."

Actually it doesn't, as I demonstrated here.

Unfortunately, unlike the Monty Hall problem I am unable to come up with a quick and easy way of using people's faith in the wrong answer to separate them from their money. That's usually the best explanatory device for this sort of thing.
posted by tkolar at 3:27 PM on February 16, 2008

It seems to me (and I know I'm missing something) that logic dictates that one, two, or three people would kill themselves on those days. If there are up to five blue eyed people, then you get two bonus deaths from deduction because one, two, or three are predictable, and you can predict the actions of BEP-2, and if they don't behave as expected, you have to add yourself to the number. But with six people, there's no reason for anyone to think that anyone knows the color of their own eyes on the basis of the statement "someone has blue eyes".
Put it this way - if logic dictates that on day 100 all the blue eyed people hike to the square, and none of the brown eyed people do, how again would they know which group they were in? I think if no one heads for the square in the first five days, then no one ever does. If you're not one of three (we know how that goes down) or one of five (where that two step removal brings your theory of mind down to that third person, so things play out as predictably) - then nothing happens and no one kills themselves.
posted by moxiedoll at 3:30 PM on February 16, 2008

I liked your answer, tkolar, because it is closer to mine than to the answer that is, apparently correct. I see what the majority is saying though, though, for the small numbers. If it's A B and C, then A thinks that B thinks that C is the only BEP and will kill himself. When C makes no move toward death, A thinks "ah! now B gets it and knows that C can see another BEP. Surely B & C will off themselves tomorrow" when they *don't*, C knows there's another person, and he knows it's him. (obviously they're all thinking this, at each other). So on day three, they all march off. If it's three, or four or five (because the "I think they think" thing gets you two steps removed from the true number) then death. Otherwise - I don't think there's any death.
posted by moxiedoll at 3:37 PM on February 16, 2008

So, tkolar, just so we're clear: you're claiming you see something that's eluded Terence Tao? I'm not snarking or implying that's impossible or saying we should all bow to Authority, but the guy is about as big an authority as there is on this stuff, so I wanted to get the claim explicit. (Me, even if I held your views, I'd be a little more 'umble about putting them forth in the circs, but that's just me.)
posted by languagehat at 3:39 PM on February 16, 2008

Assigning this assumption unto the subject's thinking is a choice by the problem-solver and isn't implicit within the problem statement. What happens if one decides to accommodate the uncertainty within their thinking?

Gyan, I'll repeat: it's not a psychological problem. You're ignoring or misunderstanding the part of the problem definition that states,

“All the tribespeople are highly logical and devout, and they all know that each other is also highly logical and devout (and they all know that they all know that each other is highly logical and devout, and so forth).”

That's an instruction to disregard the sort of mental gymnastics you keep bringing up. You're not meant to regard it as some sort of social thought-experiment, as Tao says in the web page it's expositing the Common Knowledge concept of logic and set theory.

Obviously, if this scenario took place in anything like the real world, the outcome would be nothing like the outcome of this puzzle.
posted by XMLicious at 3:48 PM on February 16, 2008

I don't get why people think this the logic extends for 2, 3, or 4 people but then breaks down. Every day that nobody commits suicide is another piece of information. That's why statements like:

Because of this mutual deadlock nobody is expected to commit suicide and nobody does.

Day two rolls around and the same deadlock exists.
Day three ....


...blows my mind. It's not the same deadlock.

Put yourself in their shoes. You don't know what eye color you have. Let's say including you, there are 10 people on the island. Here's how it plays out depending on how many of those 10 people are blue eyed.

1: As soon as the statement is made, the guy with blue eyes realizes that no one he sees has blue eyes, therefore he does. He announces this the next day.

2: Each blue-eyed sees the other blue-eyed guy, thinks "well, since he doesn't see anybody else with blue-eyes, he knows he's the only one" and waits for the next day. When the other guy doesn't say anything the next day, they each realize that the other guy must see someone with blue eyes. Since they see that everyone else on the island has brown eyes, then that other person must be themselves. Bingo, they announce this on the second day.

3: Each blue-eyed guy sees two blue-eyed guys. Each looks up his trusty little guide (outlined above) and says "if there are only 2 blue-eyed guys, they will announce this on the second day." When they don't, each realizes that the other two guys must see more than one other blue-eyed guy. Well since everyone else on the island has brown eyes, then that other guy must be himself. Bingo, announce this on the third day.

4: Each blue-eyed guy sees three blue-eyed guys. Each looks up his trusty little guide (outlined above) and says "if there are only 3 blue-eyed guys, they will announce this on the third day." When they don't, each realizes that the other three guys must see more than two other blue-eyed guys. Well since everyone else on the island has brown eyes, then that other guy must be himself. Bingo, announce this on the fourth day.

5: Each blue-eyed guy sees four blue-eyed guys. Each looks up his trusty little guide (outlined above) and says "if there are only 4 blue-eyed guys, they will announce this on the fourth day." When they don't, each realizes that the other four guys must see more than three other blue-eyed guys. Well since everyone else on the island has brown eyes, then that other guy must be himself. Bingo, announce this on the fifth day.

6: Each blue-eyed guy sees five blue-eyed guys. Each looks up his trusty little guide (outlined above) and says "if there are only 5 blue-eyed guys, they will announce this on the fifth day." When they don't, each realizes that the other five guys must see more than four other blue-eyed guys. Well since everyone else on the island has brown eyes, then that other guy must be himself. Bingo, announce this on the sixth day.

7: Each blue-eyed guy sees six blue-eyed guys. Each looks up his trusty little guide (outlined above) and says "if there are only 6 blue-eyed guys, they will announce this on the sixth day." When they don't, each realizes that the other six guys must see more than five other blue-eyed guys. Well since everyone else on the island has brown eyes, then that other guy must be himself. Bingo, announce this on the seventh day.

8: Each blue-eyed guy sees seven blue-eyed guys. Each looks up his trusty little guide (outlined above) and says "if there are only 7 blue-eyed guys, they will announce this on the seventh day." When they don't, each realizes that the other seven guys must see more than six other blue-eyed guys. Well since everyone else on the island has brown eyes, then that other guy must be himself. Bingo, announce this on the eighth day.

9: Each blue-eyed guy sees eight blue-eyed guys. Each looks up his trusty little guide (outlined above) and says "if there are only 8 blue-eyed guys, they will announce this on the eighth day." When they don't, each realizes that the other eight guys must see more than seven other blue-eyed guys. Well since everyone else on the island has brown eyes, then that other guy must be himself. Bingo, announce this on the ninth day.

10: Each blue-eyed guy sees nine blue-eyed guys. Each looks up his trusty little guide (outlined above) and says "if there are only 9 blue-eyed guys, they will announce this on the ninth day." When they don't, each realizes that the other nine guys must see more than eight other blue-eyed guys. Well since everyone else on the island has brown eyes, then that other guy must be himself. Bingo, announce this on the tenth day.

At what point does this line of statements become false?
posted by turaho at 4:30 PM on February 16, 2008 [1 favorite]

I knew I should have previewed. The penultimate sentence in example 10 should read "Well since there's no one else left on the island that isn't accounted for, then..."
posted by turaho at 4:32 PM on February 16, 2008

I am unable to come up with a quick and easy way of using people's faith in the wrong answer to separate them from their money.

Switch it so that instead of killing themselves when they realize their eye color, the members of this island win a trillion dollars when they deduct what color their eyes are--and if they're wrong, their entire family is killed before their eyes.

Heck, even better. Stick me in a room with 99 other people. Make everyone wear either a red or blue hat. Announce that you will ask every five minutes if someone knows for sure what color their hat is, given the fact that at least one person is wearing a blue hat. If I'm wearing a blue hat, I guarantee that I win your money every goddamned time, no matter how many other people are wearing blue hats.
posted by turaho at 4:39 PM on February 16, 2008

(As long as everyone is playing to win a trillion dollars and not just to trick me into watching my family killed before me.)

Okay, I'm done now.
posted by turaho at 4:41 PM on February 16, 2008

Could you explain it again and START with the reality of six without explaining what would happen to one or two or three or five? If there are six, and I'm one of them, we're all thinking there are either five or six BEP. None of us KNOW what color our own eyes are. We all know there are five others, and the fewest BEP we can think anyone else might know of is FOUR because we know that each other guy doesn't know their own color, and we don't know about our own color. So you're saying we all kill ourselves on day six? WHY? If none of us knows our own color on day 1 or two why do we know *our own color* on day six? I get how the passing of days work for the first three, or for one who believes that someone else believes that there are three, but I'm not going to concern myself with the one, two, or three day scenarios (per the handy guide) because each of us knows that those don't apply. So the early scenarios that alert you to your own eye color aren't going to happen, nor can I impute knowledge to someone based on one of those scenarios that can be proven or disproven based on their actions. So if there are actually six, how is their eye color revealed to them?
(again, I know that I'm wrong, but I don't know why).
posted by moxiedoll at 5:05 PM on February 16, 2008

So, tkolar, just so we're clear: you're claiming you see something that's eluded Terence Tao? I'm not snarking or implying that's impossible or saying we should all bow to Authority, but the guy is about as big an authority as there is on this stuff, so I wanted to get the claim explicit. (Me, even if I held your views, I'd be a little more 'umble about putting them forth in the circs, but that's just me.)

Let me say this precisely then: Terence Tao has missed the boat on this one.

The problem of multiple entities who are all making decisions based on their own perspective of shared information is directly analogous to the router clusters that make up the internet. I've never faced this particular problem in network topology, but I've faced enough similar ones that I'm very comfortable with the concept of considering systems from the point of view of N logical entities at the same time.

Deadlock is not a terribly uncommon result in these sorts of systems, so I wasn't particularly surprised when one emerged at a certain size.

Any computer programmers who want to test my solution can do so easily in any object oriented language -- although what is more likely is that while writing the logic for the "villager" object they'll realize what I'm talking about and not bother finishing the simulation.
posted by tkolar at 5:34 PM on February 16, 2008

I find this comment on the original page convincing. It's similar to what tkolar has said.

(i) Say there is 1 blue-eyed person (’BEP’) on the island. The traveler’s statement will tell this person they are blue-eyed (because that person sees no other BEP) and that person will kill themselves.

(ii) Say there are 2 BEP on the island. Each will know there is 1 BEP, 998 brown-eyed people, and themselves (eye colour unknown). Each will be able to determine their own eye colour from the actions of the other BEP. On the appropriate day, if the other BEP were to kill themselves, the person would have to have brown eyes (as the dead BEP would not have seen any other BEP). If the person were *not* to kill themselves, however, that would mean the person has blue eyes, as the other person would have been waiting for the same determination. Next day both will have to kill themselves.

(iii) Say there are 3 BEP on the island. The idea is to extend this pattern to the 3rd BEP: each BEP knows that there are 2 BEP, 997 brown-eyed people, and themselves (eye colour unknown). Each BEP could then determine their own eye colour from the actions of the other 2 BEP: if they were to have brown eyes, the 2 BEP would be stuck in the same situation as above, and would end up killing themselves. When the other 2 BEP do not kill themselves at the appointed time, however, the person knows they must *not* be brown-eyed, and thus must kill themselves. Each BEP has this perspective, and so all BEP must kill themselves on the next day.

But in (iii) is where I think a mistake is made. If there are 3 or more BEP, such as in (iii), then each BEP knows something they do not in (i) or (ii), which is that every BEP (regardless of their own eye colour) knows that there is at least one other BEP. So only with 3 or more BEP in the group is it common knowledge - i.e. known to every member of the group - that *every other member of the group knows* that there is at least 1 BEP. This is different from the idea that “everybody knows there is at least 1 BEP”, which would be true in (ii).

So in both (iii) and the problem’s stated 100 BEP case, the traveler’s statement actually does not change the tribespeople’s situation, i.e. it does not give any person new information about the number of BEP. Each already knows that there is at least 1 BEP, *and* each already knows that everyone else already knows there is at least 1 BEP. Nobody starts questioning; that is, the chain of reasoning that results in many (probably grisly) demises cannot begin under these circumstances because the reasoning in (i) - and (ii) - is not consistent with this knowledge.

posted by Pater Aletheias at 5:57 PM on February 16, 2008

tkolar - I understand what you're saying but I would object that this isn't like some form of agent-based modeling. The islanders aren't acting independently. It's an integrated system, not something where the behavior of each individual would necessarily be coded separately. Whether or not anyone kills themselves on a given day is a form of communication between the islanders, who aren't allowed to discuss eye color in any way (and thereby they cannot plan out another way to figure this out).

Remember, with this fictitious religious perspective the islanders want to kill themselves if they have blue eyes, it's not something they're trying to avoid or play rock-paper-scissors with.

Because they all understand all of the nuances we've been talking about here, they actually don't even need to pay attention until the day I expressed as β-1 up above; obviously if they can see 99 or 100 blue-eyed people they already know nothing is going to happen on days 1 to 98.

To put it another way, they don't even think about killing themselves on days 1 to 98. The only reason they wait is because of the two constraints that they can't discuss this and that they only have the opportunity to kill themselves once per day.
posted by XMLicious at 6:34 PM on February 16, 2008

The islanders aren't acting independently.

On the contrary. Because they are not allowed to discuss eye color they are *forced* to act independently. The only thing they can react to is what they see, which in this case is N or N-1 blue-eyed people and whether or not anyone has committed suicide.

Believe me, the islanders map very directly onto objects in a computer program. Much better than they map onto actual humans.

Because they all understand all of the nuances we've been talking about here...

Not to single you out, but there's been a horrendous amount of this "of course they all know they must kill themselves on day n+1" stuff in this thread. The problem says nothing about everyone knowing this -- it's something that they would have to logically deduce from the rules as presented.

And for N >= 4, it can't be logically deduced from the rules as presented.
posted by tkolar at 7:46 PM on February 16, 2008

I wrote...
So -- ten people, four blueys, six brownies. quonsar stirs shit up.

Day one rolls around and everyone on the island can see at least see at LEAST three blueys. Let's call them A, B, and C. Any given observer will reach the following conclusions:

A can see both B and C so he has no reason to suspect that he's a bluey
B can see both A and C so he has no reason to suspect that he's a bluey
C can see both A and B so he has no reason to suspect that he's a bluey

Because of this mutual deadlock nobody is expected to commit suicide and nobody does.

If someone can explain to me either the flaw in the logic above, or what new information is made available by no one committing suicide on days 2, 3, 4, 5 etc. I will happily back down on this.
posted by tkolar at 7:56 PM on February 16, 2008

Tkolar, I think it does happen with only three. Like this:
Ok, so it's as you laid it out. With A, A has no reason to suspect he's a bluey, so he thinks - ahh - B and C each think that the other one is the only one with blue eyes, so A expects B and C to expect that C and B will kill themselves on day one. BUT NO ONE DOES. A thinks - ahh! now they get that they are seeing each other's blue eyes, and so it'll happen on day two. BUT IT DOESN'T. Since B and C can't see their own eyes (but they can see A) this makes A realize that B and C are each seeing TWO blue eyed people. Just like he he did. A knows he's the third, since everyone else's eyes are brown.
(B and C, of course, make the same deductions as to the other two, simultaneously).
So they all off themselves on day three.
Do you think that's wrong?
posted by moxiedoll at 8:11 PM on February 16, 2008

Here's my longer articulation of it, but:

On day 0 the blues see 3 blues and know there either must be 3 or 4 blues and the browns see 4 blues and know there are either 4 or 5 blues. Everyone is precisely able to predict the behavior of the other islanders, so each of the blues know that if no one has killed themselves on day 3, he is himself a blue. Each of the browns thinks that if no one has killed themselves on day 4, he is a blue, but of course that's not what happens.

Each islander knows that there are only two possible states of affairs and the actions of the blue islanders he can see (i.e. either killing themselves or not killing themselves on either day β-1 or day β) tells him which of those two states of affairs is the true one. That is the new information that is introduced. (Note that the value of β in my formulation is different for the blues versus the browns: it's the number of blues the islander can see.)

A deadlock, like a threading deadlock, is when multiple objects place conflicting holds on the same resource and it happens because each individual object cannot anticipate the actions of the other objects. That is not the case here.
posted by XMLicious at 8:24 PM on February 16, 2008

Tkolar, I think it does happen with only three.

I follow your reasoning and I suspect that it's right, but I'm not confident enough either direction to commit to it. The reason I chose N=4 is that it was the lowest number that I was absolutely certain of the logic for.

Certainly if at any point any person is expecting someone to kill themselves and they don't, new information is being added to everyone's pool.

The deadlock only occurs when nobody expects anyone to kill themselves, and nobody does.
posted by tkolar at 8:28 PM on February 16, 2008

Everyone is precisely able to predict the behavior of the other islanders, so each of the blues know that if no one has killed themselves on day 3, he is himself a blue.

Once again: The islanders do *not* know this, as it is not logically derivable when N >= 4.

...like a threading deadlock...

A threading deadlock is very different beast than what we're discussing here.
posted by tkolar at 8:34 PM on February 16, 2008

Everyone is precisely able to predict the behavior of the other islanders, so each of the blues know that if no one has killed themselves on day 3, he is himself a blue.

Once again: The islanders do *not* know this, as it is not logically derivable when N >= 4.

...like a threading deadlock...

A threading deadlock is very different beast than what we're discussing here.
posted by tkolar at 8:34 PM on February 16, 2008

With all due respect tkolar, logical constructs exist in the same universe as mathematical formulas: they don't break down just because the variables get bigger.

The fact that no one has committed suicide after 2, 3, 4, 5 etc., days pass IS the new information that is made available.

There is no mutual deadlock thanks to mutual knowledge, as that wiki entry explains. For those of us who can't interpret modal expressions at a glance (I'm with ya there), I believe turaho spells it out as plainly as I ever could, but I'll try: Every bluey sees n-1 blueys. When those n-1 people haven't offed themselves after n-1 days, all blueys realize they are one of the n. Simple as that. Like any good formula, it holds true for n=1 to 1,000,000.

The part that confused me the most was how the visitor gave them any new information. The key was figuring out that he gave them new information and not new knowledge, in that he made that knowledge common. Sure, they knew that blueys existed on the island, but until that moment, they couldn't have been sure when they first collectively knew that. Without that information, they could not collectively determine n.

Curses to languagehat, who kept me up all night thinking of this.

On preview:
The deadlock only occurs when nobody expects anyone to kill themselves, and nobody does.

Thanks to common knowledge and the passing of time, there is no longer any denying the number of blueys, therefore the highly analytical islanders would most certainly be expecting some death with their afternoon tea. There's the flaw in your logic.
posted by dgbellak at 8:36 PM on February 16, 2008

Maybe my problem is that I'm basing my reasoning on the idea that there's "news". I know many are asserting that it's stupid to think 10 is different than 3, but it seems to me that the "news" factor is limited to <6 blueys.
If one - it's news to him! dead.
if two - news to them that the other one isn't the only one! dead.
if three - news to them that the other two don't realize that it should be news to them - dead.
if four or five - can deduct knowledge about yourself, and / or one other person's self knowledge - so four or five expect another party to play out the three people scenario (when they don't - dead).
In any of these situations, there's a situation where people are getting information they didn't have before OR they can logically EXPECT that someone else is getting news. when no one reacts, they're surprised and they get the news themselves that they are the one preventing things from playing out like they expected.
With six, no one's getting any news, nor is anyone EXPECTING that anyone would, hypothetically (by subtracting himself and the actor) be surprised by lack of death.
posted by moxiedoll at 8:50 PM on February 16, 2008

Once again: The islanders do *not* know this, as it is not logically derivable when N >= 4.

Yes it is, it's derivable through induction. That's the point of Tao saying that the islanders are “highly logical” and know that the others are highly logical: they are each certain that all of the others have gone through the same induction steps and that the blues are now able to kill themselves based upon it, whether that includes “me” in each case or not.

A threading deadlock is very different beast than what we're discussing here.

A threading deadlock is a circular reference just like the other kinds of programming deadlock that I'm familiar with. You might have a different definition but Wikipedia agrees with me and also that the solution to it involves developing a way for each object or process to anticipate the actions of the others:

“Deadlock can be avoided if certain information about processes is available in advance of resource allocation.”

dgebellak : The part that confused me the most was how the visitor gave them any new information.

The visitor didn't give them new information really, just an unspoken common point in time to pace everything off of. As someone pointed out in the thread on Tao's page it could also happen based upon the birth of a blue-eyed child.
posted by XMLicious at 8:51 PM on February 16, 2008

Your flaw begins with day one:

Day one rolls around and everyone on the island can see at least see at LEAST three blueys. Let's call them A, B, and C. Any given observer will reach the following conclusions:

A can see both B and C so he has no reason to suspect that he's a bluey
B can see both A and C so he has no reason to suspect that he's a bluey
C can see both A and B so he has no reason to suspect that he's a bluey

Because of this mutual deadlock nobody is expected to commit suicide and nobody does.

That holds true...until after 2 days when 2 of those 3 haven't done the deed. There is no deadlock, only an indeterminate variable, which they will be able to determine with time. At that point it becomes unavoidable - the three now know there is a third, as each one of those 2 other can clearly see 2 blueys rather than one, and since they can see no one else has blue eyes, they now know that all three of them have blue eyes.

This does not break down for more than 3 people.
posted by dgbellak at 8:57 PM on February 16, 2008

As someone pointed out in the thread on Tao's page it could also happen based upon the birth of a blue-eyed child.

Only at the point of collective awareness (the point at which everyone knows not only of the child but of the point at which everyone else is aware of the child), which is new information. If just one sees the birth, that is not enough to determine n.
posted by dgbellak at 9:00 PM on February 16, 2008

With all due respect tkolar, logical constructs exist in the same universe as mathematical formulas: they don't break down just because the variables get bigger.

Actually, it's set theory and it happens all the time.

turaho does an excellent job of presenting what the interation would look like if it was valid, but it is based on the same flawed assumption that the "inductive" argument is -- namely, that you can look at N objects and always be able to draw the same logical conclusions as you can with N-1.

This is not true, *particularly* where it concerns a process of boolean elimination. In very small sets you can eliminate objects based on the fact that they are the only possible candidate for a particular condition -- when the sets grow large enough that type of elimination is no longer possible because no one object is the only possible candidate.

The same issue is at the root of this problem. *IF* there was any person on the island who could actually see just one or two sets of blue eyes then they could perform an elimination and get the ball rolling -- but there's not. For N=4, everyone on the island sees at least three pairs, sees the deadlock, and nobody does anything.
posted by tkolar at 9:12 PM on February 16, 2008

If just one sees the birth, that is not enough to determine n.

Well, everyone has to together see something they can use as a triggering event, yes. But at all times each islander knows that n is either his β or his β+1, the triggering event doesn't add to that knowledge.
posted by XMLicious at 9:15 PM on February 16, 2008

tkolar, induction doesn't involve the assumption you mention above. It involves a step-by-step proof, which I don't think that anyone has written out.

Your idea of a deadlock here sounds as if it involve something like “I can't be a blue because I can see some other blues” but that's not so, every single islander suspects he must be a blue. He only knows he's not when the suicides of the blues he can see reveals that they each saw one less blue than him.
posted by XMLicious at 9:25 PM on February 16, 2008

Sorry, “suspects he might be a blue.”
posted by XMLicious at 9:26 PM on February 16, 2008

dgbellak wrote...
Your flaw begins with day one:

Day one rolls around and everyone on the island can see at least see at LEAST three blueys. Let's call them A, B, and C. Any given observer will reach the following conclusions:

A can see both B and C so he has no reason to suspect that he's a bluey
B can see both A and C so he has no reason to suspect that he's a bluey
C can see both A and B so he has no reason to suspect that he's a bluey

Because of this mutual deadlock nobody is expected to commit suicide and nobody does.

That holds true...until after 2 days when 2 of those 3 haven't done the deed.
Okay, I'm listening...

There is no deadlock, only an indeterminate variable, which they will be able to determine with time.

If no one is expecting anyone to commit suicide and no one commits suicide, what information is being added to the system that allows them to determine the variable?
posted by tkolar at 9:30 PM on February 16, 2008

tkolar, induction doesn't involve the assumption you mention above. It involves a step-by-step proof, which I don't think that anyone has written out.

No kidding, that's why "induction" was in quotes. An inductive "proof" like the one provided by Terry Tao wouldn't last five minutes in a discrete mathematics class.
posted by tkolar at 9:32 PM on February 16, 2008

Your idea of a deadlock here sounds as if it involve something like “I can't be a blue because I can see some other blues” but that's not so, every single islander suspects he must be a blue.

The heart of my deadlock is that if there are N blue eyed people on island, none of them are able to deduce with certainty that they should kill themselves, and *everyone knows this*.

So unlike the case where you keep expecting someone to deduce that they need to kill themselves -- in which case the fact that someone doesn't kill themselves gives you new information -- you're stuck.
posted by tkolar at 9:38 PM on February 16, 2008

If no one is expecting anyone to commit suicide...

That's quite a big leap you're taking, and it ignores the very rules set forth in the problem. You're changing the argument. You are failing to explain why the "truthful and completely logical" islanders would arbitrarily stop applying logical reasoning after 3 days.

...and no one commits suicide, what information is being added to the system that allows them to determine the variable?

The very fact that no one has committed suicide is added information. Every day that passes without incident will provide more of this information, even after 3 days. There is no reason to assume that the islanders will suddenly stop paying attention to this fact after 3 days under the belief that their "truthful and completely logical" brethren simply failed to figure it out.

Also, from your original comment:

...has no reason to suspect that he's a bluey

That is not a logical conclusion to make. Your adding unknown information to the argument. If he does not know his own eye color, he could not logically form a conclusion one way or the other, and would therefore be equally as open to the possibility that he has blue eyes as to the possibility that he does not. He would "suspect" nothing.
posted by dgbellak at 10:12 PM on February 16, 2008

Right. I've definitely reached the point where I've exhausted my explanatory abilities and feel like I'm just talking past other people. I suspect others may feel the same way about me. I'm calling it a night, and will consider the whole thing with fresh eyes tomorrow.
posted by tkolar at 10:18 PM on February 16, 2008

XMLicious: That's an instruction to disregard the sort of mental gymnastics you keep bringing up

And as I'm trying to say in other words, it's the mental gymnastics that lead to the notion to wait for n-1 days before deducing one's own eye colors. Elaborate the mechanics of how any person in the game comes to have that notion to wait for n-1 days. It's not an axiom.

DevilsAdvocate: It doesn't make a difference whether a BEI assumes he's non-blue-eyed (which is refuted on day 100), or makes no assumption at all about his eye color (and discovers he's blue-eyed on day 100)

But when he's simulating the thoughts of others recursively, he has to fill in the placeholders for the assumptions and knowledge of others all the way down the nested levels. It's not clear to me that the situation resolves to the same result as assuming that one is non-blue-eyed and that everyone else will do the same. In n = 5, A can see 4 BEIs and, say, allow uncertainty over his own eye color. So, he thinks that there are atleast 4 BEIs and maybe 5. Now, when he's modeling B's thoughts - he can't assume that B sees 3 BEIs. B either sees 3 BEIs or 4 BEIs. A doesn't know which, so he has to accommodate both. B doesn't know what C sees. So, in A's thoughts about B's thoughts about C's thoughts, the permutations of possible thoughts increase..etc. Take this to 99 nesting levels and I don't know if A arrives at the theorem that if there are no suicides by Day 99, then I'm a BEI.
posted by Gyan at 10:34 PM on February 16, 2008

But in (iii) is where I think a mistake is made. If there are 3 or more BEP, such as in (iii), then each BEP knows something they do not in (i) or (ii), which is that every BEP (regardless of their own eye colour) knows that there is at least one other BEP.

Yes, but they don't know that every BEP person knows that every BEP knows that there is at least one BEP.

For example, three BEP, pragmatically named A, B, and C.

A knows the following about eyes:

• A: A knows nothing about A's eyes.
• B: A knows B's eyes are blue.
• C: A knows C's eyes are blue.

A knows the following about what B knows about eyes:

• A: A knows B knows the color of A's eyes.
• B: A knows B knows nothing about B's eyes.
• C: A knows B knows C's eyes are blue.

A knows the following about what B knows about what C knows about eyes:

• A: A knows B knows C knows the color of A's eyes.
• B: A knows B knows C knows the color of B's eyes.
• C: A knows B knows C knows nothing about C's eyes.

So, note well: A does not know that B knows that C knows that there's a blue-eyed person.

After the stranger makes his announcement, A does know that B knows that C knows that there's a blue-eyed person.

This can be extended indefinitely; it doesn't stop at 3 (just like it doesn't stop at 2, or even 1, which some people in this thread think it does). It's exactly why the induction works.

For example, here it is with six BEP:

A knows:

• A: A knows nothing about A's eyes.
• B: A knows B's eyes are blue.
• C: A knows C's eyes are blue.
• D: A knows D's eyes are blue.
• E: A knows E's eyes are blue.
• F: A knows F's eyes are blue.

A knows that B knows:

• A knows that B knows the color of A's eyes.
• A knows that B knows nothing about B's eyes.
• A knows that B knows that C's eyes are blue.
• A knows that B knows that D's eyes are blue.
• A knows that B knows that E's eyes are blue.

A knows that B knows that C knows:

• A knows that B knows that C knows the color of A's eyes.
• A knows that B knows that C knows the color of B's eyes.
• A knows that B knows that C knows nothing about C's eyes.
• A knows that B knows that C knows that D's eyes are blue.
• A knows that B knows that C knows that E's eyes are blue.
• A knows that B knows that C knows that F's eyes are blue.

A knows that B knows that C knows that D knows:

• A knows that B knows that C knows that D knows the color of A's eyes.
• A knows that B knows that C knows that D knows the color of B's eyes.
• A knows that B knows that C knows that D knows the color of C's eyes.
• A knows that B knows that C knows that D knows nothing about D's eyes.
• A knows that B knows that C knows that D knows that E's eyes are blue.
• A knows that B knows that C knows that D knows that F's eyes are blue.

A knows that B knows that C knows that D knows that E knows:

• A knows that B knows that C knows that D knows that E knows the color of A's eyes.
• A knows that B knows that C knows that D knows that E knows the color of B's eyes.
• A knows that B knows that C knows that D knows that E knows the color of C's eyes.
• A knows that B knows that C knows that D knows that E knows the color of D's eyes.
• A knows that B knows that C knows that D knows that E knows nothing about E's eyes.
• A knows that B knows that C knows that D knows that E knows that F's eyes are blue.

A knows that B knows that C knows that D knows that E knows that F knows:

• A knows that B knows that C knows that D knows that E knows that F knows the color of A's eyes.
• A knows that B knows that C knows that D knows that E knows that F knows the color of B's eyes.
• A knows that B knows that C knows that D knows that E knows that F knows the color of C's eyes.
• A knows that B knows that C knows that D knows that E knows that F knows the color of D's eyes.
• A knows that B knows that C knows that D knows that E knows that F knows the color of E's eyes.
• A knows that B knows that C knows that D knows that E knows that F knows nothing about F's eyes.

Again, note well: A does not know that B knows that C knows that D knows that E knows that F knows that there's a blue-eyed person.

After the stranger's announcement, that changes: A now does know that B knows that C knows that D knows that E knows that F knows there's a blue-eyed person.

Don't make me do this for the hundred case, please. It's exactly the same principle; it would just involve a whole lot more levels of "knows that knows that knows that knows that".

There is no "deadlock". After any number. There are just varying levels of "knows that knows that knows that" which various posters in this thread fail to successfully comprehend.
posted by Flunkie at 11:15 PM on February 16, 2008 [1 favorite]

The visitor didn't give them new information really, just an unspoken common point in time to pace everything off of.

He definitely gave them new information.

After his announcement, everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that everyone knows that there is at least one blue eyed person.

None of the islanders knew this fact before the announcement. NONE of them. Now, they all know it.

And that added piece of information is enough to kill them.

All right, that's it, I'm going to bed.
posted by Flunkie at 11:44 PM on February 16, 2008 [2 favorites]

No kidding, that's why "induction" was in quotes. An inductive "proof" like the one provided by Terry Tao wouldn't last five minutes in a discrete mathematics class.

It's not just Tao's problem, he's repeating a classic one. He may be teaching a class more advanced than discrete math and consequently breezed over it. Or he might just not be good at articulating these things.

Here's one inductive proof, it could certainly be formulated many different ways:

Hypothesis: The m blue-eyed people I can see committed suicide m days after quonsar stirred shit up. This means that each one firmly concluded that there were m blue-eyed people on the island including himself. If I had blue eyes they would have concluded that there were m+1 blue-eyed people on the island the way I would if I had blue eyes. Therefore I must not have blue eyes.

Basis Step, m=1: The 1 blue-eyed person I can see committed suicide 1 day after quonsar stirred shit up. This means that he firmly concluded he was the only blue-eyed person on the island. If I had blue eyes he would have concluded that there were 2 blue-eyed people on the island the way I would if I had blue eyes. Therefore I must not have blue eyes.

It's counter-intuitive like most induction proofs and it's only true in the contrived narrowly-defined parameters of the puzzle but it's genuine induction.
posted by XMLicious at 12:01 AM on February 17, 2008

For doubters of the mass suicide: this comment on the original link explains very precisely what new information the visitor gives to the islanders. I see, on preview, that Flunkie has explained this as well.

I'm going to go through the train of thought in the n=5 case. I know it's long. I'm going for precision. Square brackets indicate editorial comments.

BEGIN
There are 5 blue-eyes: A, B, C, D and E. The foreigner makes their gaffe.

A reasons as follows:
I, A, see four blue-eyes. I will perform a thought experiment. Suppose I am not blue-eyed. Then B will reason thus:

I, B, see three blue-eyes. [Recall, in A's thought experiment, A has supposed they themself are not blue-eyed. The hypothetical B will thus know that A's eyes are not blue.] I will perform a thought experiment. Suppose I am not blue-eyed. Then C will reason thus:

I, C, see two blue-eyes. [Recall, A is supposing they themself are not blue-eyed, and in A's thought experiment, B is supposing they themself are not blue-eyed.] I will perform a thought experiment. Suppose I am not blue-eyed. Then D will reason thus:

I, D, see one blue-eye. [A has supposed they themself are not blue-eyed, in A's thought experiment B is supposing they are not blue-eyed, and in B's thought experiment, C is supposing they themself are not blue-eyed.] I will perform a thought experiment. Suppose I am not blue-eyed. Then E will reason thus:

I, E, see no blue-eyes. But I know there is one. I must be it. I will kill myself tomorrow.

I, D, have finished my thought experiment. If I have non-blue eyes, E will kill themself on day 1. Thus, if E does not kill themself on day 1, I must have blue eyes, in which case I will kill myself on day 2 (along with E).

I, C, have finished my thought experiment. If I have non-blue eyes, E will kill themself on day 1, or D and E will kill themselves on day 2. Since I have more information than D did in my thought experiment, I know that E will not kill themself on day 1. So if I have non-blue eyes, D and E will kill themselves on day 2. If they do not do so, then I must have blue eyes, and I will kill myself on day 3 (along with D and E).

I, B, have finished my thought experiment. If I have non-blue eyes, either D and E will kill themselves on day 2, or C, D and E will kill themselves on day 3. Since I have more information than C did in my thought experiment, I know that D and E will not kill themselves on day 2. So if I have non-blue eyes, C, D and E will kill themselves on day 3. If they do not do so, then I must have blue eyes, and I will kill myself on day 4 (along with C, D and E).

I, A, have finished my thought experiment. If I have non-blue eyes, either C, D and E will kill themselves on day 3, or B, C, D and E will kill themselves on day 4. Since I have more information than B did in my thought experiment, I know that C, D and E will not kill themselves on day 3. So if I have non-blue eyes, B, C, D and E will kill themselves on day 4. If they do not do so, then I have blue eyes, and I will kill myself on day 5 (along with B, C, D and E).

A's reasoning is complete. A will wait to see if B, C, D and E kill themselves on day 4. As outside observers, we know that B, C, D and E will reason exactly as A did, and so will wait to see if anyone kills themselves on day 4. (Note that A does not know that B, C, D and E have reasoned exactly as A has, since B, C, D and E know A's eyes are blue, whereas A does not know that they know this.) So all blue-eyes wait until day 4, observe that no one kills themselves. Each blue-eye concludes that they have blue eyes and kills themself the next day.

END

Of course, if you want to do n=6, just consider all of A's reasoning as being conducted as a thought experiment by another blue-eyed person P who supposes they are not blue eyed, and thus concludes that if no one kills themselves on day 6, then P themself is blue eyed.

It's important to note that what B, C, D and E think in the various thought experiments is not what the actual islanders B, C, D and E think. This is because A has supposed they themself do not have blue eyes, but the actual B, C, D and E know this is not the case.

If you rewrite this whole thing before the foreigner spills the beans, when you get down to what the hypothetical E thinks, you see that E cannot draw any conclusions about their eye color, so they do nothing. So no one else can make any conclusions, either. This is how everyone lives before the foreigner shows up.

Gyan's confusion stems from supposing that in the nested experiments, A must guess at what the others know. But this isn't the case: it is a supposition of the thought experiment that A has non-blue eyes. I tried to indicate this in the square bracketed comments.

Final notes:
1. If the foreigner never comes, but a new blue-eyed baby is born (who somehow immediately has the same faculties for reasoning and suicide as the adults), no one kills themselves. Proof left as exercise for the reader.
2. Tao's inductive proof is fine.
posted by samw at 12:17 AM on February 17, 2008 [1 favorite]

samw wrote...
I'm going to go through the train of thought in the n=5 case. I know it's long. I'm going for precision. Square brackets indicate editorial comments.

Thank you for writing this out. Let me point out exactly where I disagree with you and perhaps we can make forward progress:

A reasons as follows:
I, A, see four blue-eyes. I will perform a thought experiment. Suppose I am not blue-eyed. Then B will reason thus:

With you so far.

I, B, see three blue-eyes. [Recall, in A's thought experiment, A has supposed they themself are not blue-eyed. The hypothetical B will thus know that A's eyes are not blue.] I will perform a thought experiment. Suppose I am not blue-eyed. Then C will reason thus:

Still here.

I, C, see two blue-eyes.

And now we have a problem. A [who is thinking all of this] knows for a fact that C can see at least three sets of blue eyes. A also knows that B -- having started with the exact same starting conditions -- knows the same thing.

In fact everyone knows that if they can see M blue-eyes, then the minimum anyone else is seeing is M - 1.

So what I'm not following is why A would continue down the train of thought when it has led to a provably false hypothetical.
posted by tkolar at 1:25 AM on February 17, 2008

samw: Gyan's confusion stems from supposing that in the nested experiments, A must guess at what the others know. But this isn't the case: it is a supposition of the thought experiment that A has non-blue eyes.

As I mentioned above, if the supposition is allowed, then the suicides follow, but the relevant part of the problem statement only says,

...
All the tribespeople are highly logical and devout, and they all know that each other is also highly logical and devout (and they all know that they all know that each other is highly logical and devout, and so forth).
for the purposes of this logic puzzle, “highly logical” means that any conclusion that can logically deduced from the information and observations available to an islander, will automatically be known to that islander.

It is Tao's proof which assigns the assumption to each BEI:

Each blue-eyed person will reason as follows: “If I am not blue-eyed, then..."

Factoring in uncertainty, this is n = 3

01)A knows that B is BEI
02)A knows that C is BEI
03)A is unsure of his own EC - he could be a BEI

A thinks that B sees
either

04)1 BEI
05)2 BEI

A thinks that B thinks there are
either

06)1 or 2 BEI or
07)2 or 3 BEI

A thinks that B thinks that C sees
either

08)0 BEI
09)1 BEI
10)2 BEI

A thinks that B thinks that C thinks there are
either

11)0 BEI
12)1 BEI
13)1 or 2 BEI
14)2 or 3 BEI

After foreigner's address

(11) is discarded

If C actually held (08), then C figures his EC as blue, adopts (12) but A doesn't know what B thinks that C thinks.
There's no suicide and none expected on Day 1

Now B is left with (06),(07) and (B(C)) with (13),(14) within A's mind

Suicide is again uncertain and hence unexpected the next day.
When there's no suicide on Day 2, I tentatively think there's no evolution in the statespace, and hence a stalemate (unless assumptions are now introduced). But if not, why not?
posted by Gyan at 2:03 AM on February 17, 2008

Just to clarify on that, the logical contradiction A reaches is that

1) In his thought experiment, B has proposed a C who can only see two blue-eyes.
2) In reality, he knows that B knows that no one on the island can be seeing less than three blue-eyes.

Since his thought experiment has led to a situation that contradicts reality, I would expect A to consider assumptions that he made for the experiment invalid.
posted by tkolar at 2:05 AM on February 17, 2008

Uh, that was clarifying my comment, not Gyan's.
posted by tkolar at 2:07 AM on February 17, 2008

1) In his thought experiment, B has proposed a C who can only see two blue-eyes.
2) In reality, he knows that B knows that no one on the island can be seeing less than three blue-eyes.

No, tkolar, he (being A) does not know that B knows that no one on the island can be seeing less than three blue-eyes.

B knows that no one on the island can be seeing less than three blue-eyes (in fact, B knows there are at least four).

And A knows that too.

But A doesn't know that B knows that. Which is what you're claiming in (2).
posted by Flunkie at 9:28 AM on February 17, 2008

tkolar writes (quoting me):

"I, C, see two blue-eyes."

And now we have a problem. A [who is thinking all of this] knows for a fact that C can see at least three sets of blue eyes. A also knows that B -- having started with the exact same starting conditions -- knows the same thing.

This is not the case. A does not know that B knows that C sees at least three blue-eyed people. In fact, B does know that C sees at least three blue-eyed people, but A does not know B knows this because A does not know that B knows that A's eyes are blue. Remember the B in A's thought experiment does not have the same knowledge that the real B does. In the thought experiment, A has supposed they themself have non-blue eyes, so the imaginary B will know this. But the real B knows that A does have blue eyes. So the real B and the B imagined by A are working from different sets of facts. (On preview, Flunkie agree's with my assessment.)

One must be very careful to separate what each islander knows from what each islander knows the others know, and from what each islander knows the other know the others know, etc. You are confusing some of these.

Gyan: You say that if suppositions are allowed, then the suicides will happen. Good: logical people can suppose things for the purposes of deduction. If n=3, A gets:
If I am not blue-eyed, and if B assumes they are not blue-eyed, then B thinks C will kill themself on day 1.
If I am not blue-eyed, and if B assumed they are blue-eyed, then B and C will kill themself on day 2.
Either way, A knows that if day 2 passes with no deaths, it is because A themself has blue eyes.

If A supposes they themself have blue eyes, they will deduce that B and C will both wait to see what happens on day 2.

On day 2, no one kills themselves, and the scenario when A has non-blue eyes is contradicted. But the scenario where A has blue eyes is still possible. So A knows they have blue eyes.

The problem with your argument, Gyan, is that you didn't write down which suppositions lead to which beliefs. This is the extra structure that makes all the difference.
posted by samw at 9:33 AM on February 17, 2008

tkolar:

2) In reality, he knows that B knows that no one on the island can be seeing less than three blue-eyes.

Just in case it is not still clear why this is a false statement, I want you to think about it a little more:

You're claiming that A knows that B knows that no one on the island can be seeing less than three blue-eyes.

In particular, for example, you're claiming that A knows that B knows that C sees at least three blue-eyes.

There are, in reality, five blue-eyed islanders. A, B, C, D, and E.

So please name three or more islanders that A knows that B knows that C knows have blue eyes.

I'll give you D and E. But that still leaves one. The only three possibilities left for that one are A, B, and C.

So now please explain exactly why A knows that B knows that C knows that at least one of A, B, and C has blue eyes.
posted by Flunkie at 9:45 AM on February 17, 2008

A crazy Russian maths head gave me a variant of this as a puzzle during a job interview for a dotcom during Bubble 1.0. Luckily I'd read it before as part of an AI undergrad. My brain still hurts.
posted by meehawl at 10:19 AM on February 17, 2008

samw, they can suppose, but they don't have to, and with 99 BEIs, there's a whole lotta suppositions to assume, and whose implications to work out. Is there a solution that doesn't rely on inducting from n=1 or 2 or 3 or assuming that the basic pattern remains true of large numbers?
posted by Gyan at 11:17 AM on February 17, 2008

with 99 BEIs, there's a whole lotta suppositions to assume, and whose implications to work out.

First, so what? Second, induction is a standard method that allows you to work out many, many implications in one fell swoop, without needing to work them all out individually.

Is there a solution that doesn't rely on inducting from n=1 or 2 or 3 or assuming that the basic pattern remains true of large numbers?

Yes. Manually work out all of the implications, each one individually, exactly as samw did.

What samw did is not induction. Induction is a standard logical shortcut that you can use to quickly and easily get to exactly the same conclusion that is reached via the extremely labor intensive method that samw demonstrated.

This question of yours really kind of strikes me as being, essentially, "Is there a solution that doesn't rely on the islanders understanding the basics of formal logic, or else on the islanders being able to correctly keep track of many individual manually derived implications?"

No. No, there's not.
posted by Flunkie at 11:54 AM on February 17, 2008

2) In reality, [A] knows that B knows that no one on the island can be seeing less than three blue-eyes.

No, tkolar, he (being A) does not know that B knows that no one on the island can be seeing less than three blue-eyes.

In reality (not his thought experiment) he absolutely knows that everyone on the island can see three people with blue eyes. Because he can see four people with blue eyes.

In reality (not the thought experiment) he sees B, C, D, and E all of whom have blue eyes.

He can trivially deduce that

1) B can see C, D, and E
2) C can see B, D, and E
3) D can see B, C, and E
4) E can see B, C, and D

And just for completeness, he himself can see

5) B, C, D, and E

So I repeat, every one on the island knows that if they can see M blue-eyes, then the minimum anyone else is seeing is M - 1.
posted by tkolar at 12:08 PM on February 17, 2008

So please name three or more islanders that A knows that B knows that C knows have blue eyes.

This is my whole point. A is running a thought experiment and *Given the assumptions of the experiment* he reaches a contradiction between the experiment and a known fact. He has run into a situation where B accepting the existence of a "only-sees-two-blueys" when he knows that B would never accept that though simple observation.

Therefore his thought experiment is based on false assumptions, therefore he ends it.
posted by tkolar at 12:14 PM on February 17, 2008

He has run into a situation where B accepting the existence of a "only-sees-two-blueys" when he knows that B would never accept that though simple observation.

Rephrase for clarity:

A has run into a situation where his hypothetical B is using the existence of a "only-sees-two-blueys" C in a thought experiment, when he knows that the real B would never accept the existence of an "only-sees-two-blueys" C. He therefore concludes that his initial assumptions have lead him astray.
posted by tkolar at 12:28 PM on February 17, 2008

tkolar writes (quoting Flunkie):

"No, tkolar, he (being A) does not know that B knows that no one on the island can be seeing less than three blue-eyes."

In reality (not his thought experiment) he absolutely knows that everyone on the island can see three people with blue eyes. Because he can see four people with blue eyes."

True, but this does not contradict what Flunkie said! Flunkie said:
A doesn't know that B knows that C sees at least three blue eyes.

You said:
A does know that B sees three blue eyes.

Both of these statements are correct! Thus A has not, as far as A knows, assumed anything contradictory.

tkolar writes "A has run into a situation where his hypothetical B is using the existence of a 'only-sees-two-blueys' C in a thought experiment, when he knows that the real B would never accept the existence of an 'only-sees-two-blueys' C. He therefore concludes that his initial assumptions have lead him astray."

He does not know that the real B would not accept the existence of an "only-sees-two-blueys". B in fact would not accept the existence of such a C, but A does not know that B would not accept the existence of such a C.

Gyan: Flunkie said it better than I could have.
posted by samw at 12:37 PM on February 17, 2008

tkolar:

A has run into a situation where his hypothetical B is using the existence of a "only-sees-two-blueys" C in a thought experiment, when he knows that the real B would never accept the existence of an "only-sees-two-blueys" C.

No. He does not know that.

A knows B sees three or more blueys.

A knows C sees three or more blueys.

B knows C sees three or more blueys.

A does not know that B knows that C sees three or more blueys.

I honestly don't know how to explain this more clearly than I already have, so I'm going to repeat my challenge to you, which you don't seem to have addressed:

You're claiming that A knows B knows C knows there are three or more blueys.

So name them.

Name three or more individuals that A knows B knows C knows have blue eyes.
posted by Flunkie at 12:48 PM on February 17, 2008

samw wrote...
He does not know that the real B would not accept the existence of an "only-sees-two-blueys". B in fact would not accept the existence of such a C, but A does not know that B would not accept the existence of such a C.

I'm glad we've been able to bring this down to a single point that we disagree on, but I'd say we've pretty much reached a deadlock where we both believe that we see obvious things that the other person isn't getting. I, for one, have explained my point in every way I know how to given the limited medium of text.

So, thank you for your time and consideration, and good day.

Flunkie wrote...
You're claiming that A knows B knows C knows there are three or more blueys.

So name them.

I explained that here, but apparently not clearly enough. I'm all out.
posted by tkolar at 12:59 PM on February 17, 2008

No, tklolar, what you showed there was:

(1) A knows B knows there are at least three blueys.
(2) A knows C knows there are at least three blueys.
(3) A knows D knows there are at least three blueys.
(4) A knows E knows there are at least three blueys.

I disagree with none of that, and none of them are a response to the question that I've asked you.

You've shown that A knows everyone knows there are at least three blueys.

You have not shown that A knows that B knows that everyone knows that there are at least three blueys.
posted by Flunkie at 1:03 PM on February 17, 2008

Again, just name them. Please.

Please, name three people that A knows B knows C knows have blue eyes.
posted by Flunkie at 1:04 PM on February 17, 2008

Well, tkolar, I'm sorry you feel that way. You're insisting that B knowing something is the same thing as A knowing B knows it. But they aren't the same. I don't know how you can think they're the same! They aren't! A knows that B knows that everyone can see 2 blue-eyes, but A doesn't know that B knows that everyone can see three blue-eyes because A doesn't know that B knows that A's eyes are blue. But if you're done, then I guess that's fine.
posted by samw at 2:08 PM on February 17, 2008

holy crap you guys use a lot of words for a "no wai!/srsly, wai!" back and forth.
posted by juv3nal at 3:41 PM on February 17, 2008

Flunkie: the accepted solution (for n=100) requires induction, as Tao uses. It assumes that the structure for 100 is the same as that for 3, only more layers. The hypothesis for induction assumes that inherently:

If I am not blue-eyed, then there will only be n-1 blue-eyed people on this island, and so they will all commit suicide n-1 days after the traveler’s address

Is there a solution besides manual calculations that doesn't rely on that assumption? My essential question is given uncertainty and a large n, can it be shown that there is no stalemate where A cannot choose between two competing hypothesis?
posted by Gyan at 12:10 AM on February 18, 2008

Gyan, I still don't get the way you're talking about uncertainty and manual calculations as if the islanders would try to go and confirm the induction or something. The certainty is the inductive proof, not some sort of “well he would think that he would think that he would think…” thing. Those are explanatory examples being brought up here in the thread.

Obviously this would never happen IRL but the assumption of the problem is that the islanders would all be able to arrive at things like inductive proofs and would act based on them.
posted by XMLicious at 2:08 AM on February 18, 2008

Gyan, again, you seem to be asking "Is there a solution that doesn't rely on the islanders understanding that solution?"

And again, the answer is no. No, there's not a solution that doesn't rely on the islanders understanding that solution.
posted by Flunkie at 6:40 AM on February 18, 2008

Don't the first two blue-eyed citizens commit suicide on the second noon after the second one comes into consciousness? Why is an outsider needed?
posted by Mental Wimp at 4:10 PM on February 18, 2008

Don't the first two blue-eyed citizens commit suicide on the second noon after the second one comes into consciousness?

You mean if nobody makes an announcement like the stranger made? If so, then no.

Why is an outsider needed?

Well, think about it from the point of view of one of them. Let's say the first.

You're on this island. Everybody else on the island has brown eyes. Your eyes are blue, but you don't know that.

A blue-eyed person "comes into consciousness".

A day passes. He hasn't killed himself.

Why do you think that means that you have blue eyes?

He would have only killed himself after a day if he knew, the day he came into consciousness, the color of his eyes.

Why would he have known that?
posted by Flunkie at 4:27 PM on February 18, 2008

Ok,

I didn't believe at first, but I do now. Let me take a crack:

My problem was that it seems asinine to deduce down to the point where anybody on the island would think that they are the only BEI. Obviously everyone can see there are tons of them.

What helped me is realizing that this is all a mind game that an islander plays inside his own head.

BEI A thinks, I'll assume I'm brown eyed. That means there are 99 Brown eyed Islanders. My friend B, whom I know is Blue eyed, is also thinking that he is brown eyed. If I'm brown eyed, And he thinks he's brown eyed, then he thinks there are only 98 Blue eyed people. A knows full well that B is wrong about this, but B doesn't. A also thinks - B is a smart guy, and he is thinking about his friend C, whom both of us (A&B) know is blue eyed, but he probably thinks he is brown eyed too. However, because A is thinking about B, thinking about C, then now our hypothetical C believes there are only 97 BEI. A knows full well that C doesn't actually think this: this isn't the real C, but imaginary C that lives in imaginary B's mind who lives in A's mind. This is the part that I didn't quite grasp before - There is nobody who actually thinks that there are less than 99 BEI, but rather there are nested subpopulations within islander A's mind, where the islander at each step assumes they are brown eyed.


To illustrate, consider case for N=26

Islanders A-Z are Blue eyed, the rest are brown eyed.

The following all goes on inside A's head

I assume I am brown, leaving 25 Blue
Brown: A Blue:BCDEFGHIJKLMNOPQRSTUVWXYZ

However, B can assume he is brown, which means he thinks this:
Brown:AB Blue:CDEFGHIJKLMNOPQRSTUVWXYZ [in A's mind, B thinks A is brown]

[A thinking about] B thinking about C:
C assumes he is brown, which means he thinks this:
Brown:ABC Blue:DEFGHIJKLMNOPQRSTUVWXYZ [again, this is not what C actually thinks, this is what A thinks that B thinks that C thinks]

[A thinking about B thinking about] C thinking about D:
D can assume he is brown, which means he thinks this:
Brown:ABCD Blue:EFGHIJKLMNOPQRSTUVWXYZ

and so on...

At each step, each Islander assumed they are brown and considers the rest of the population. Therefore at each step, the number of hypothetical Blue eyers gets reduced by one, until:

[A thinking about B thinking about C thinking about D thinking about...] X thinking about Y:
Y assumes he is brown, which means he thinks this:
Brown:ABCDEFGHIJKLMNOPQRSTUVWXY Blue:Z --- Haha Z must be the Blue, and tomorrow he will kill himself. If he doesn't, then I must be Blue too.

Remember this is not the real Y's thought process, this is the imaginary Y that lives in imaginary X's head who lives in imaginary W's head.... who all live in [the real] A's head.

Anyhow, the next day, Z is still alive, so imaginary Y has to kill himself (as well as Z of course). But, neither Y nor Z are dead the second day, and imaginary X has a problem: the problem is that imaginary Y doesn't exist! the premise for imaginary Y was imaginary X's premise that only Y and Z were blue (imaginary X thought this because he was a figment of imaginary W's mind tho thinks that A-W are all brown...). Anyway, now imaginary X needs to kill himself on day 3, because he knows that not only are Y and Z blue, but he is too. But when X doesn't kill himself, imaginary W realizes that he is wrong and he too must be blue...

Each day we unwrap the hypothetical recursion one more step, and one more hypothetical islander realizes he is blue eyed. But nothing happens in reality because all this drama is only going on inside A's head, and is conditioned on a bunch of false assumptions, namely that each BEI thinks he is brown

A doesn't actually expect anything to happen until day 25. Because A can see that B-Z are all blue eyed, and he knew that the assumption that each hypothetical islander made about having brown eyes was false. He fully expected it the whole think to unwind until day 25 when B would realize that B is the 25th BEI, and they would kill themselves

When this doesn't happen, A realizes that he too was wrong, and that he too must be a BEI.
posted by jpdoane at 8:42 PM on February 18, 2008 [1 favorite]

My last comment:

XMLicious, Flunkie: again, the inductive hypothesis that n-1 BEIs will kill themselves after n-1 days is not a first principle. It's a pattern inferred from the mental gymnastics. So, the inductive proof assumes that the pattern holds without regard for the magnitude of n, and so all that is left to do is demonstrate the claim for n=1 and then induct along the line of positive integers. My key objection is that the inductive hypothesis begs the question, and that the inductive proof isn't a mathematical proof; it's a psychological proof, since it involves simulating the thinking of a potential BEI. And if one presupposes the correspondence between number of BEIs and the days before suicides, then the pattern is trivial to extend for a thinker.
posted by Gyan at 6:11 AM on February 19, 2008

I guess it's just a fundamental disagreement. Like I've said above, I don't regard this as a psychological issue at all, the induction proof and the behavior resulting from it is an oblique means of communication between these fictional hyperintelligent, hypermathematical islanders.
posted by XMLicious at 8:20 AM on February 19, 2008

To put it another way: I don't know about induction, but psychology and this “Theory of Mind” thing you kept mentioning are definitely not first principles in a mathematical / logic puzzle.
posted by XMLicious at 8:25 AM on February 19, 2008

This is about seven kinds of sidetrack, but the discussion of Theory of Mind¹ in conjunction with the (varying playful and earnest) mentions of autism as a confounding factor in the discussion of another, very different puzzler² made me blink³ when I came across a mention of this article on the speculation that autism is essentially an impairment of the (uniquely human?) neurophysical function of ToM.

¹Which, regardless, I agree with XMLicious as being completely outside the bounds of the freakin' logic puzzle this post is about. Not to say I don't enjoy the wander, but it's like trying to pour ketchup on a word problem about french fries—that's ceci n'est pas une hamburger.

²You might be surprised how much joy I've gotten from having a reason to search for autistic viking. It's like I've been waiting my whole life to do that, but I didn't know it until the moment arrived.

³Metaphorical blinking.<sup>4

4</sup>Which is kind of funny, because odds are I literally blinked a whole bunch while reading it. But I'd argue that the article itself did not cause me to blink—I would have blinked even if I hadn't been reading it.
posted by cortex at 9:13 AM on February 19, 2008 [1 favorite]

OK, Flunkie, I got it. Thanks.
posted by Mental Wimp at 10:20 AM on February 19, 2008

Gyan: The "mental gymnastics" you reference are deductions from the premises including that each islander is a strictly logical thinker. That is, they can use deduction properly and can induce a chain of deductions from an initial deduction. It really doesn't have a psychological component beyond this. If they were computers programmed to use inductive chains of deductions, they would behave the same way, as long as they were given the knowledge that the others were such as well. If they were allowed psychological quirks, such as denial, then the deduction would not work and so the inductive chain would break down.
posted by Mental Wimp at 10:28 AM on February 19, 2008

So, the inductive proof assumes that the pattern holds without regard for the magnitude of n

No. No, it does not.

Induction is a very explicit and very specific method of proof.

One of the steps that must be taken in a proof by induction - any proof by induction - is proving that the pattern holds without regard for the magnitude of n.

That is done in every inductive proof. Specifically, it was done in this inductive proof.

There is no assumption that this pattern holds without regard for the magnitude of n. There was a proof of that fact.
posted by Flunkie at 3:30 PM on February 19, 2008

inductive proof isn't a mathematical proof

No offense, but try telling that to a mathematician. You should count yourself lucky if he only laughs behind your back.
posted by Flunkie at 3:32 PM on February 19, 2008

I'm sorry, that was mean, even though I said "no offense". To put it less meanly:

Proof by induction is as fundamental to, and as accepted by, mathematicians as is the idea that the two facts:

• If x is true, then y is true
• x is true

when taken together, imply that y is true.
posted by Flunkie at 3:38 PM on February 19, 2008

You guys keep pulling me back in.

This is Tao's proof, with my emphasis:

Now suppose inductively that n is larger than 1. Each blue-eyed person will reason as follows: “If I am not blue-eyed, then there will only be n-1 blue-eyed people on this island, and so they will all commit suicide n-1 days after the traveler’s address”. But when n-1 days pass, none of the blue-eyed people do so (because at that stage they have no evidence that they themselves are blue-eyed). After nobody commits suicide on the (n-1)^{st} day, each of the blue eyed people then realizes that they themselves must have blue eyes, and will then commit suicide on the n^{th} day.

The inductive hypothesis is presupposed, which is fine, since that's the whole point of a proof by induction, but it is the assignment of a psychological activity to an individual, which is begging the question in a puzzle involving belief-driven behavior by sentient beings. In a mathematical proof, you don't show contingent validity for n+1 by having people "realize" the conclusion. You have to show why any person would think the inductive hypothesis assigned in the first place. And for the last time, the IH is not a first-principle. Also, if each person presupposes that they are not BEI for the purposes of simulation, then suicides clearly follow. But if they leave their own status in limbo, and assume the same by others, then I don't know that the same solution obtains.

Flunkie, in comment about inductive proof not being mathematical, I was referring to this one in particular, not generally.

/over and out
posted by Gyan at 5:00 AM on February 20, 2008

it is the assignment of a psychological activity to an individual, which is begging the question in a puzzle involving belief-driven behavior by sentient beings.

That's taken care of by the assumption that the islanders are highly logical. As the puzzle states:

for the purposes of this logic puzzle, “highly logical” means that any conclusion that can logically deduced from the information and observations available to an islander, will automatically be known to that islander.

This is a logic puzzle, not a psychological puzzle. We're not meant to take the possible irrationality or stupidity of the islanders into account. Saying "maybe the islanders wouldn't make the correct inferences" is akin to saying, "maybe someone has green eyes" or "maybe the island will sink into the sea before the third day."
posted by painquale at 11:39 AM on February 20, 2008

I have read this entire thread in one sitting over the course of my workday. I have blue eyes. I'm going to go gouge them out now.

[Seriously, big ups to Flunkie, OmieWise, and samw, who helped me get it.]
posted by desjardins at 12:35 PM on February 20, 2008

Gyan, seriously, is your objection anything other than, essentially, "maybe they don't think that others would understand the logic involved"?

Because if that's your objection, you're not going to find anyone who disagrees. If one of the islanders thinks maybe some blue-eyed islander won't comprehend, then he's not going to kill himself. Agreed. Completely. Is that it?
posted by Flunkie at 3:48 PM on February 20, 2008