My write-up of the "Blue Eyes" solution (SPOILER A

[skullturf]

Yeah, I'm reiterating points that have been made earlier, but it's important to understand that the following are all different. (Say A, B, C,... are blue-eyed people.)

A's mental model of the island (in which 1 person has unknown eye color, and 99 people definitely have blue eyes)

A's mental model of B's mental model of the island (in which 2 people have unknown eye color, and 98 people definitely have blue eyes)

A's mental model of B's mental model of C's mental model of the island (in which 3 people have unknown eye color, and 97 people definitely have blue eyes)

and so on.

The fact that there are 99 blue-eyed people is not common knowledge.

The fact that there are 98 blue-eyed people is not common knowledge either.

Neither is the fact that there are 97 blue-eyed people.

And neither is the fact that there is at least one blue-eyed person!

[Tinman42]

Yeah, I'm reiterating points that have been made earlier, but it's important to understand that the following are all different. (Say A, B, C,... are blue-eyed people.)

A's mental model of the island (in which 1 person has unknown eye color, and 99 people definitely have blue eyes)

A's mental model of B's mental model of the island (in which 2 people have unknown eye color, and 98 people definitely have blue eyes)

A's mental model of B's mental model of C's mental model of the island (in which 3 people have unknown eye color, and 97 people definitely have blue eyes)

and so on.

The fact that there are 99 blue-eyed people is not common knowledge.

The fact that there are 98 blue-eyed people is not common knowledge either.

Neither is the fact that there are 97 blue-eyed people.

And neither is the fact that there is at least one blue-eyed person!

The fact that there are at least 99 people with blue eyes is common knowledge because everyone can see 99 people with blue eyes.

The fact that everyone knows there are at least 98 people with blue eyes is common knowledge because everyone can see at least 99 people with blue eyes.

If I can see 99 people with blue eyes, then the least number of people with blue eyes that you can see is 98. This is If I make the assumption that I have brown eyes.

Also, the guru said "there is some one with blue eyes", how is this not common knowledge? Even if your theory is correct all the way down to 2 pairs of blue eyes, it can not be the case for 1 pair of blue eyes, because this was stated to everyone making it common knowledge. (this is "assuming everyone heard it and believes it and knows everyone else heard it and believes it, but to assume they didn't is not in the spirit of the riddle)

[lightvector]

Yeah, I'm reiterating points that have been made earlier, but it's important to understand that the following are all different. (Say A, B, C,... are blue-eyed people.)

A's mental model of the island (in which 1 person has unknown eye color, and 99 people definitely have blue eyes)

A's mental model of B's mental model of the island (in which 2 people have unknown eye color, and 98 people definitely have blue eyes)

A's mental model of B's mental model of C's mental model of the island (in which 3 people have unknown eye color, and 97 people definitely have blue eyes)

and so on.

The fact that there are 99 blue-eyed people is not common knowledge.

The fact that there are 98 blue-eyed people is not common knowledge either.

Neither is the fact that there are 97 blue-eyed people.

And neither is the fact that there is at least one blue-eyed person!

The fact that there are at least 99 people with blue eyes is common knowledge because everyone can see 99 people with blue eyes.

The fact that everyone knows there are at least 98 people with blue eyes is common knowledge because everyone can see at least 99 people with blue eyes.

If I can see 99 people with blue eyes, then the least number of people with blue eyes that you can see is 98. This is If I make the assumption that I have brown eyes.

Also, the guru said "there is some one with blue eyes", how is this not common knowledge? Even if your theory is correct all the way down to 2 pairs of blue eyes, it can not be the case for 1 pair of blue eyes, because this was stated to everyone making it common knowledge. (this is "assuming everyone heard it and believes it and knows everyone else heard it and believes it, but to assume they didn't is not in the spirit of the riddle)

Definition: A fact F is common knowledge if:

(1) Everyone knows F.
(2) Everyone knows "Everyone knows F".
(3) Everyone knows "Everyone knows "Everyone knows F"".
(4) Everyone knows "Everyone knows "Everyone knows "Everyone knows F""".
... etc

The fact that there are at least 99 people with blue eyes is NOT common knowledge. Imagine you're one of the people, and you can see 99 people with blue eyes but you don't know your own eye color. Maybe your eye color really isn't blue, perhaps it really is the case that you have brown eyes and everyone else has blue eyes. So for all you know, everyone else sees 98 blue eyes and 1 brown eye. This means that (2) is false, because you don't know that "Everyone knows that there are at least 99 people with blue eyes".

The fact that there are at least 98 people with blue eyes is also NOT common knowledge. If you work it out carefully, you will find that (3) is false. Similarly, for 97 eyes, you will find that (4) is false, and so on. So none of these is common knowledge.

The guru's statement that there is someone with blue eyes does become common knowledge, after the guru has said it. skullturf's post was referring to what the islanders know before the guru has said anything, in which the existence of at least one blue-eyed person is not common knowledge (because statement 100 in the previous list would be false).

[Tinman42]

You are telling me that not everyone on this island (perfect logicians mind you) knows that there is at least one person with blue eyes? and they not everyone know that everyone knows. and not every one knows that every one knows that every one knows that at least one person has blue eyes?

If me and two friends were standing in a group, and we all had bblue eyes. even without communicating, I am pretty certain we would all know there is at least two people in the group with blue eyes, we would all know that everyone knows there is at least 1 person with blue eyes and we would all know that everyone knows this. We are not perfect logicians. I still do not understand how this is not universal. We may not know that we know that we know ETC. that there are at least 2 pairs of blue eyes, but we could all figure it out to at least one pair. So, at a larger number (100) of blue eyes, how could perfect logicians not figure out immediatley that everyone knows theres at least 1 pair of blue eyes? (again, assuming that no one is blind or closing their eyes or whatever)

[Dason]

You are telling me that not everyone on this island (perfect logicians mind you) knows that there is at least one person with blue eyes? and they not everyone know that everyone knows. and not every one knows that every one knows that every one knows that at least one person has blue eyes?

If me and two friends were standing in a group, and we all had bblue eyes. even without communicating, I am pretty certain we would all know there is at least two people in the group with blue eyes, we would all know that everyone knows there is at least 1 person with blue eyes and we would all know that everyone knows this. We are not perfect logicians. I still do not understand how this is not universal. We may not know that we know that we know ETC. that there are at least 2 pairs of blue eyes, but we could all figure it out to at least one pair. So, at a larger number (100) of blue eyes, how could perfect logicians not figure out immediatley that everyone knows theres at least 1 pair of blue eyes? (again, assuming that no one is blind or closing their eyes or whatever)

Because that's not what's being said. The main confusion is the misinterpretation of what "common knowledge" means. It means something other than what you're thinking apparently. Sure everybody knows that there is at least one person with blue eyes. But it's not true that everybody knows that everybody knows that everybody knows that .... everybody knows... that everybody knows... (goes on forever).... until the guru speaks up.

[skullturf]

Once again, EACH of the following statements is DIFFERENT. Every sentence in the list means something different from the next sentence in the list.

"Everybody knows that X"
"Everybody knows that everybody knows that X"
"Everybody knows that everybody knows that everybody knows that X"

and so on.

Depending on what X is, some statements in the list could be true and others could be false.

[lightvector]

You are telling me that not everyone on this island (perfect logicians mind you) knows that there is at least one person with blue eyes?

Wrong. Everyone on the island does know there is at least one person with blue eyes.

and they not everyone know that everyone knows. and not every one knows that every one knows that every one knows that at least one person has blue eyes?

Wrong. They do all know this. What they don't yet know is "Everyone knows that everyone knows that everyone knows that everyone knows that ... (repeated a total of 100 times) that at least one person has blue eyes". They know it up to 99 repetitions, but not 100 repetitions, which they only learn once the guru speaks.

If me and two friends were standing in a group, and we all had bblue eyes. even without communicating, I am pretty certain we would all know there is at least two people in the group with blue eyes,

Correct.

we would all know that everyone knows there is at least 1 person with blue eyes

Correct.

and we would all know that everyone knows this.

Wrong. Let's work through it. You don't know your own eye color. All you know is that you have 2 blue-eyed friends with you.

Don't even assume you have blue eyes. For all you know, it's a genuine possibility that you have brown eyes. So put yourself in that situation. You have 2 blue-eyed friends, and you really don't know your own eye color, you suspect they truly might be brown. In such a case, if your eyes were brown, what would your first friend know?

Your first friend would think to himself "Hmmm, your eyes are brown, and I don't know my own eye color. So friend 2 might be the only one in our group with blue eyes. Then friend 2, being the only one with blue eyes and not knowing his own eye color, would not know if there was anyone in our group with blue eyes".

Of course, you'd know better. You know that friend 1 has blue eyes, so friend 2 would know of a blue-eyed person of this group, namely friend 1. But friend 1 doesn't know his own eye color, so friend 1 wouldn't know that friend 2 knew.

All of the above is assuming your eyes are brown.

Now, if your eyes are blue, friend 1 WOULD know that friend 2 knows because then friend 1 could see that friend 2 saw your eyes, even though friend 1 doesn't know his own eye color.

So to summarize:

If your eyes are brown, friend 1 does NOT know that friend 2 knows (about the existence of a blue-eyed person in the group).
If your eyes are blue, friend 1 does know friend 2 knows (about the existence of a blue-eyed person in the group).

You don't know your own eye color, so you don't know which of these is the case. So you DON'T know whether or not friend 1 knows that friend 2 knows that there is at least one blue-eyed person.

Therefore, it is NOT true that everyone knows that everyone knows that everyone knows that there is at least one blue-eyed person in the group.

[tempest69]

A brown eyed person knows that the number (of blues) is either 100 or 101, as he can see 100 people with blue eyes.
He knows that the other browns know that 102, 101, or 100 is the correct value.
He knows that the blues know that 99,100, or 101 is the correct answer.
He is aware that blues may suspect other blues of thinking that there are 98 blue eyed islanders.


A blue eyed person knows the number of blues is 99 or 100, as he can see 99 people with blue eyes.
he knows the other blues know that 98,99, or 100 is the correct value.
he knows the brown's know that 99, 100, or 101 is the correct answer
he knows that the brown may suspect other browns of thinking there are 102 blue eyed islanders.

*note, brown is considered any non-blue color for the purpose of logic.

Anyway a reasonable algorithm, assuming that they want off the island quickly would be:
If one of the "knows" is divisible by 4 use that as your pick (yup 100)-- otherwise
Locate the low value which is divisible by 4 in our patch of 98..102 (the suspect range) that all of the islanders can deduce.
100, We subtract 4 to ensure that we start outside of the suspect range. (Breaking on fours ensures that all islanders use the same start)
(perfect logicians could make it work with 3's instead of fours.. I'm tired)

Then we start. at 96.. if you see only 95 other islanders with blue eyes, it's your night to get on the ship.
Then day 97 if you see only 96 other blue eyes, it's time to go.
day 98--97
day 99--98 (first day anyone expects their blue eyed brethren might leave)
day 100... all of the blue eyed only see 99 other blue eyed islanders. so it's time to leave,
all of the brown eyed know that there were at least 100 and don't get to the ship.

____________
Anyway I suspect the clip function should work reasonably well, though I'm not convinced that all edge cases are handled.

[Goldstein]

day 100... all of the blue eyed only see 99 other blue eyed islanders. so it's time to leave

For a minute there, there was some pretty whacky stuff going on in your post that made me think you don't mean this. I don't even know where to start, so I won't.

[jestingrabbit]

A brown eyed person knows that the number (of blues) is either 100 or 101, as he can see 100 people with blue eyes.
He knows that the other browns know that 102, 101, or 100 is the correct value.
He knows that the blues know that 99,100, or 101 is the correct answer.
He is aware that blues may suspect other blues of thinking that there are 98 blue eyed islanders.


A blue eyed person knows the number of blues is 99 or 100, as he can see 99 people with blue eyes.
he knows the other blues know that 98,99, or 100 is the correct value.
he knows the brown's know that 99, 100, or 101 is the correct answer
he knows that the brown may suspect other browns of thinking there are 102 blue eyed islanders.

*note, brown is considered any non-blue color for the purpose of logic.

Anyway a reasonable algorithm, assuming that they want off the island quickly would be:
If one of the "knows" is divisible by 4 use that as your pick (yup 100)-- otherwise
Locate the low value which is divisible by 4 in our patch of 98..102 (the suspect range) that all of the islanders can deduce.
100, We subtract 4 to ensure that we start outside of the suspect range. (Breaking on fours ensures that all islanders use the same start)
(perfect logicians could make it work with 3's instead of fours.. I'm tired)

Then we start. at 96.. if you see only 95 other islanders with blue eyes, it's your night to get on the ship.
Then day 97 if you see only 96 other blue eyes, it's time to go.
day 98--97
day 99--98 (first day anyone expects their blue eyed brethren might leave)
day 100... all of the blue eyed only see 99 other blue eyed islanders. so it's time to leave,
all of the brown eyed know that there were at least 100 and don't get to the ship.

____________
Anyway I suspect the clip function should work reasonably well, though I'm not convinced that all edge cases are handled.

The islanders can't agree on some algorithm to follow. They will simply draw what conclusions they can from their observations. They aren't trying to leave the island, they aren't trying to deduce their eye colour.

[skeptical scientist]

The islanders can't agree on some algorithm to follow. They will simply draw what conclusions they can from their observations. They aren't trying to leave the island, they aren't trying to deduce their eye colour.

There's another reason this won't work. The "suspect range" of 98-102 is based on there being 100 blue eyed people, so that, in order to design this algorithm, an individual would have to know/guess there are 100 blue-eyed people. The islanders wouldn't agree to follow this algorithm unless they knew there were 100 blue-eyed people, in which case the algorithm would be irrelevant as they'd all know their eye color anyways.

You came upon this suspect range by the following argument:

A brown eyed person knows that the number (of blues) is either 100 or 101, as he can see 100 people with blue eyes.
He knows that the other browns know that 102, 101, or 100 is the correct value.
He knows that the blues know that 99,100, or 101 is the correct answer.
He is aware that blues may suspect other blues of thinking that there are 98 blue eyed islanders.


A blue eyed person knows the number of blues is 99 or 100, as he can see 99 people with blue eyes.
he knows the other blues know that 98,99, or 100 is the correct value.
he knows the brown's know that 99, 100, or 101 is the correct answer
he knows that the brown may suspect other browns of thinking there are 102 blue eyed islanders.

However, there's absolutely no reason why a brown-eye should consider what blues suspect other blues know and not consider what browns suspect other browns know, or why a blue-eye should consider what browns suspect other browns know and not what blues suspect other blues know. It only makes sense to consider both, or neither, if you don't know your own eye color. In either case, the browns and the blues will end up with different suspect ranges, so they couldn't agree on an algorithm to follow without disclosing the number of blue-eyed individuals they see (at which point everyone goes away).

[douglasm]

The islanders can't agree on some algorithm to follow. They will simply draw what conclusions they can from their observations. They aren't trying to leave the island, they aren't trying to deduce their eye colour.

Or, to put it a different way, no islander can assume any other islander is following a particular strategy unless he can prove an absolute 100% guarantee of it. They aren't mind readers, they aren't perfectly identical, and they can't communicate. Any strategy that only works if everyone spontaneously decides to follow it is invalid because the spontaneous unanimous decision required cannot be relied on.

[Binary.Tobis]

Very interesting, it's like the Monty Hall problem in terms of the "Ooooh..." moment.

I completely understand and agree with the solution even if I didn't get it myself (still thinking emotionally I guess). I was going to say that if the islanders didn't WANT to be on the island, logically they would guess every color they could think of in order of decreasing probability since there seems to be no penalty. But then I read the last bit about "No one guesses." and decided against it.

Must be like the Hypocratic Oath for Logicians: "You shall never guess until you can work to the solution and provide a proof!"

[skeptical scientist]

Very interesting, it's like the Monty Hall problem in terms of the "Ooooh..." moment.

I actually had two separate ooooh moments when I first heard the puzzle.

(The version of the puzzle I originally heard was slightly different than the one presented here.)

Spoiler:

There is a matriarchal society, and in this particular matriarchal society, there's a law, where if any woman discovers that her husband is cheating on her, she must shoot him at midnight. There's a universal taboo against discussing infidelity with the wife, so this law has never had an effect. However, everyone in the society is a huge gossip, so every woman knows whether every man (except her husband) is unfaithful. (Everyone is married.) One day, the head matriarch says, "Some man is cheating on his wife." Seven days later, everyone wakes up and all the men are dead. How many people now live in the matriarchal society?

Ooooh moment 1: There are 7 people! You can prove it by induction.
But wait a second moment: Everyone already knew what the head matriarch said. What's going on here?
Ooooh moment 2: Aha! What they learn is that everyone knows that everyone knows that...there's a cheating husband.

This is possible because the inductive argument is enough to solve the puzzle, but isn't really enough to understand what's going on, which is where the nested hypotheticals argument comes into play. The first aha moment was the discovery of the inductive argument, and the second aha moment was the discovery of the nested hypotheticals argument.

[Nitrodon]

(The version of the puzzle I originally heard was slightly different than the one presented here.)

Spoiler:

There is a matriarchal society, and in this particular matriarchal society, there's a law, where if any woman discovers that her husband is cheating on her, she must shoot him at midnight. There's a universal taboo against discussing infidelity with the wife, so this law has never had an effect. However, everyone in the society is a huge gossip, so every woman knows whether every man (except her husband) is unfaithful. (Everyone is married.) One day, the head matriarch says, "Some man is cheating on his wife." Seven days later, everyone wakes up and all the men are dead. How many people now live in the matriarchal society?

I see two problems with this formulation:

Spoiler:

1. The statement "every woman knows whether every man (except her husband) is unfaithful" needs to be common knowledge. Otherwise, the inductive step doesn't work.

2. If the head matriarch has a husband, he will never be (legally) killed as a result of that statement. Since everyone is assumed to be married, and all of the men were killed, this implies that the head matriarch is in a homosexual marriage. Thus, that option is possible in this society, and there is no way to determine how many other women were not married to men.

[skullturf]

If I had to describe my "ooooh" moment briefly, it would be something like:

In (finite but long) statements like "Everyone knows that everyone knows that everyone knows ... that everyone knows X", it matters exactly how many "layers" you have.

3 layers is a different statement from 4 layers. 98 layers is a different statement from 99 layers. We, subjectively, get confused (not unlike those stories of pre-numerate societies who count "one, two, three, many") but perfect logicians don't.

Perfect logicians have no trouble with the distinction between 2 layers, 3 layers, 4 layers, 99 layers, 100 layers, and an infinite number of layers.

[skeptical scientist]

I see two problems with this formulation.

It's true; there are multiple flaws with the formulation. Nevertheless, it was the original one I heard. Randall, when writing up his version, was very careful to avoid some of the issues in other formulations. As he puts it, "I didn't come up with the idea of this puzzle, but I've written and rewritten it over the the years to try to make a definitive version. The guy who told it to me originally was some dude on the street in Boston named Joel."

[Goldstein]

I like the implication that Joel was just hanging around on the street, trying to get the word out about the best puzzle he'd ever heard.

[tempest69]

The islanders can't agree on some algorithm to follow. They will simply draw what conclusions they can from their observations. They aren't trying to leave the island, they aren't trying to deduce their eye colour.

There's another reason this won't work. The "suspect range" of 98-102 is based on there being 100 blue eyed people, so that, in order to design this algorithm, an individual would have to know/guess there are 100 blue-eyed people. The islanders wouldn't agree to follow this algorithm unless they knew there were 100 blue-eyed people, in which case the algorithm would be irrelevant as they'd all know their eye color anyways.

You came upon this suspect range by the following argument:

A brown eyed person knows that the number (of blues) is either 100 or 101, as he can see 100 people with blue eyes.
He knows that the other browns know that 102, 101, or 100 is the correct value.
He knows that the blues know that 99,100, or 101 is the correct answer.
He is aware that blues may suspect other blues of thinking that there are 98 blue eyed islanders.


A blue eyed person knows the number of blues is 99 or 100, as he can see 99 people with blue eyes.
he knows the other blues know that 98,99, or 100 is the correct value.
he knows the brown's know that 99, 100, or 101 is the correct answer
he knows that the brown may suspect other browns of thinking there are 102 blue eyed islanders.

However, there's absolutely no reason why a brown-eye should consider what blues suspect other blues know and not consider what browns suspect other browns know, or why a blue-eye should consider what browns suspect other browns know and not what blues suspect other blues know. It only makes sense to consider both, or neither, if you don't know your own eye color. In either case, the browns and the blues will end up with different suspect ranges, so they couldn't agree on an algorithm to follow without disclosing the number of blue-eyed individuals they see (at which point everyone goes away).

Scientist: Ahh. I missed a case, good catch, that creates a jitter... and the whole thing comes crashing down. Can't have a function that calculates a nearby start for x and x+1 that works correctly.

The islanders can't agree on some algorithm to follow. They will simply draw what conclusions they can from their observations. They aren't trying to leave the island, they aren't trying to deduce their eye colour.

Jesting: I took some liberty with "perfect logicians" being able to simply know the optimal algorithm. If they aren't trying to leave the island or determine their eye colour, then I'm horribly lost and confused, and really hoping that you just made a typo.

[skullturf]

I think what was meant was: The puzzle says nothing about whether or not leaving the island is desirable. And the puzzle says nothing about whether or not knowing your eye color is desirable.

It's not about "getting to" leave the island, and it's not about "having to" leave the island.

It's just about what conclusions they can make about eye color.

The rule is "if you know your own eye color, you leave the island" but it could be anything; it might as well be "if you know your eye color, you start wearing a hat."

[skeptical scientist]

If they aren't trying to leave the island or determine their eye colour, then I'm horribly lost and confused, and really hoping that you just made a typo.

They aren't trying to leave the island or determine their eye color in the sense that is not a goal they have. They will deduce their eye color if there is sufficient info to do it (being perfect logicians) and will leave the island if they do (because those are the rules) but they aren't formulating strategies to collect enough intel to do it, because it's not like they want to leave the island. They just have to if they know their eye color, and they know everything that can be deduced from their observations.

[tempest69]

If they aren't trying to leave the island or determine their eye colour, then I'm horribly lost and confused, and really hoping that you just made a typo.

They aren't trying to leave the island or determine their eye color in the sense that is not a goal they have. They will deduce their eye color if there is sufficient info to do it (being perfect logicians) and will leave the island if they do (because those are the rules) but they aren't formulating strategies to collect enough intel to do it, because it's not like they want to leave the island. They just have to if they know their eye color, and they know everything that can be deduced from their observations.

aha. now I see,

[robot123]

I don't get it-- on Day 1, when there are 100 blue-eyed persons, won't it create a deadlock? Every night wouldn't it reset? No one would ever leave.

i.e. Night 1 - 100 blue-eyed persons each see 100 brown and 99 blue. None can conclusively determine their own eye colour. No one boards the boat. They go to sleep.
Night 2 - 100 blue-eyed persons each see 100 brown and 99 blue. None can conclusively determine their own eye colour. No one boards the boat. They go to sleep.
Night 3 - 100 blue-eyed persons each see 100 brown and 99 blue. None can conclusively determine their own eye colour. No one boards the boat. They go to sleep.

etc.

Even after 99 days, the starting point is still the same as Day 1-- the Guru is not providing any one of them enough information to build on the previous day's experience.

As far as I can understand it, as soon as you have more than 2 blue-eyed people, it will create a deadlock.

Granted, I am quite dumb. Can anyone explain to me why this isn't the case?

[skeptical scientist]

As far as I can understand it, as soon as you have more than 2 blue-eyed people, it will create a deadlock.

You believe that if there are two blue-eyed people they will leave on the second night, but if there are three, they will never leave? This is clearly inconsistent: assume that if there are two blue-eyed people, they will leave on the second night. Then if there are three, then each blue-eyed individual only sees two blue-eyed people, and hypothesizes that if there are only two blue-eyed people, they will leave on the second night. So when nobody leaves on the second night, they know there must be at least three, so their eyes must be blue.

[robot123]

As far as I can understand it, as soon as you have more than 2 blue-eyed people, it will create a deadlock.

You believe that if there are two blue-eyed people they will leave on the second night, but if there are three, they will never leave? This is clearly inconsistent: assume that if there are two blue-eyed people, they will leave on the second night. Then if there are three, then each blue-eyed individual only sees two blue-eyed people, and hypothesizes that if there are only two blue-eyed people, they will leave on the second night. So when nobody leaves on the second night, they know there must be at least three, so their eyes must be blue.

The two blue-eyed persons situation I understand-- if you see only one other blue-eyed person (let's call him Ralph) and they don't leave, that means that they too saw one other blue-eyed person, which must be you (since you only saw one). But now, add another person into the mix-- now you see two blue-eyed persons (Ralph and George). Ralph sees you and George and realizes that the Guru was talking about them (and possibly him). George sees you and Ralph and reaches the same conclusion. You see Ralph & George and come to the same conclusion.

Now that night, no one leaves.

Ralph realizes that George didn't leave because he saw you, and George realizes you didn't leave because you saw Ralph, and you realize Ralph and George didn't leave because they saw each other.

OK wait, I think I get it now.... The key is that you know that Ralph and George are perfect logicians... So if they were the only two blue-eyed persons on the island then they would have left by Night 2, but they didn't so there must be a third, which must be you.

OK never mind.

[Adam H]

Do perfect logicians necessarily have perfect memories? Could all 100 blue eyed people really make it 100 days without forgetting what day they were on?

What if some of these logicians like it on the island?

What if the boat comes right after or during the guru's pronouncement, and no one is quite sure which day is "D1"?

WHY WOULDN'T THE GURU SAY THAT THERE ARE 100 BLUE EYED PEOPLE? The jerk wasted 100 days of our miserable lives on this god-forsaken rock.

[Xias]

Do perfect logicians necessarily have perfect memories? Could all 100 blue eyed people really make it 100 days without forgetting what day they were on?

Yes.

What if some of these logicians like it on the island?

It doesn't matter whether they want to or not; if they can logically deduce their eye color, they leave the island.

What if the boat comes right after or during the guru's pronouncement, and no one is quite sure which day is "D1"?

The problem states that the boat comes at midnight, and the guru makes his announcement at noon.

WHY WOULDN'T THE GURU SAY THAT THERE ARE 100 BLUE EYED PEOPLE? The jerk wasted 100 days of our miserable lives on this god-forsaken rock.

This is Puzzland, where everyone deals with switches, hats, and towns full of liars.

[Frankels]

Hi, I think I may have an alternative solution, considering the fact that they are all perfect logicians -- if a conclusion can be logically deduced, they will do it instantly.
If so they can all leave on the first day with no help from the Guru.
If they are perfect logicians they can deduce the same optimal protocol for group separation and joining as follows:

First they all stand in a mixed group together. One separates from the group. Then another one joins this smaller group. If these two have the same eyecolour another one will join the group. However, if no one joins this group of two the person joined lastly will leave the group and will form a new group (of one)
More people join the groups one after the other, and every time someone with a different eye colour as the rest of the group joins, noone else will join, and the last person joining will leave and try a new group.
In the end if the last person joins the wrong group the other group will go back to the first (now empty) group. If that happens this person will join the other group. This person may still think he has red eyes or something so a new check is performed but as they have either blue or brown eyes that will not happen and now there are two groups: one with blue and one with brown eyes. People in the groups know their eye color is the same as the rest of the group, and thus know their own eye colour.
There may be a faster way, for instance if they divide the group into two at the beginning and rejoin if the seperation is not perfect, but as they are perfect logicians they know the optimal protocol.
If the optimal protocol is possible in various ways they have no way of knowing which protocol is being followed, and they will then revert to less optimal protocols until one is found which can only be performed in one way, such as the one I described above.

a different way to descibe this is: everyone starts joining groups of people in which everyone has the same eyecolor. groups join groups with the same eyecolor. A group with mixed eyecolours is not joined and thus disbanded. A group also disbands if someone with a different eyecolour joins (a group bigger than one that is being joined knows their own eyecolour)

Everyone leaves on the first day except the guru, unless he plays along.

[jestingrabbit]

@Frankels: You seem to be assuming that they want to leave the island. There's no reason to make that assumption. Furthermore, you seem to be claiming that there is a "best" protocol, without clearly defining best, and without proof. Finally, as it says in the original problem,

... Everyone can see everyone else at all times and keeps a count of the number of people they see with each eye color (excluding themselves), but they cannot otherwise communicate...

... it doesn't involve people doing something silly like creating a sign language or doing genetics...

You're inventing a sign language, a circumvention of the no communication restriction. In short, you're not solving the problem.

[ConMan]

Like skeptical scientist, I first heard this puzzle in a slightly different fashion (also with infidelity and gossip rather than just a visible trait like blue eyes), but I certainly agree with the solution - the one thing this thread has taught me is a better understanding of the concept of "common knowledge".

Except, in the version that I read, it just asked the question "how many islanders will leave (or hang their wives, in the version I heard), and on which night?" so it looked to answer the general version straight off. And it added an interesting twist - what happens if no-one actually has blue eyes/commited adultery, i.e. the Guru is a bold-faced liar?

Answer:

Spoiler:

Since each islander sees no-one else who fits the bill, they all assume that they're the one, a la the 1 person case. Presumably once they all arrive at the dock or execution point they break their silence and point out that in fact nobody is meant to leave/die.

[phlip]

Well yeah, the "Perfect Logician" axioms rely on the islanders not having any false knowledge... if they have any false information (in this case "the guru is trustworthy") then they can come up with false conclusions.

[rigwarl]

@Frankels: If you're allowed to have actions for people that everyone else understands, then you could just say that the rule is someone looks at you and touch their nose if you have blue eyes (and you do the same for them). But as jestingrabbit said, this is obviously a form of communication.

Regarding the Aha! moment, I couldn't understand how the Guru could say something that was obvious yet still gave information, so the example I gave myself was if a stranger walks up to me and says "Hey rigwarl!", then I know I must have met him previously and forgotten, even though he didn't explicitly tell me anything exept my own name!

[Magicaltrevor81]

Spoiler:

I'm not sure if anyone else has said this, but, essentially, the additional piece of information given by the guru is this: If you could see no-one else with blue eyes, you could leave tonight

Totally love this puzzle, by the way!

MT

[douglasm]

Spoiler:

I'm not sure if anyone else has said this, but, essentially, the additional piece of information given by the guru is this: If you could see no-one else with blue eyes, you could leave tonight

Totally love this puzzle, by the way!

MT

That fact is pretty obvious. What's not obvious, and what the 25 pages of discussion have beat into the dirt dozens upon dozens of times, is why this fact has any effect on anyone's logical analysis in light of the fact that everyone does see lots of blue eyes. It does, and the solution is correct, but the reason why is very difficult for many people to understand.

[Magicaltrevor81]

It may be obvious, but it is not known before the guru speaks.

Before the guru speaks I know that I can see 99 or 100 blue-eyed people, 99 or 100 brown-eyed people and one green-eyed person (assuming I am not the guru). Hypothetical situation: If I could see no blue-eyed people, I still would not leave the island as I don't know my eye colour.

Once the guru has spoken, the hypothetical situation above turns into a situation where I do leave the island. and the first step in the inductive reasoning is established.

[DocNasty]

Okay, completely blew thru my morning reading thru this.

And after 25 pages, I'm sorry to say that there is nobody leaving after 99 days, as I perceive the problem. They are all perfectly logical, right.

The problem I see is in this statement here:
On this island there are 100 blue-eyed people, 100 brown-eyed people, and the Guru (she happens to have green eyes). So any given blue-eyed person can see 100 people with brown eyes and 99 people with blue eyes (and one with green), but that does not tell him his own eye color; as far as he knows the totals could be 101 brown and 99 blue. Or 100 brown, 99 blue, and he could have red eyes.

It would appear that this statement at the very end:
as far as he knows the totals could be 101 brown and 99 blue. Or 100 brown, 99 blue, and he could have red eyes.
Is what creates the deadlock.

Assuming that nobody on the island knows the ratio of the colored eyes, nobody can leave the island. They have no way of knowing when to stop guessing, they wouldn't know what day (in the posted solution, 99 days, for 99 blue eyed persons). Had they known the correct ratio of blue/brown they would know when to stop counting, and then walk to the boat.

If each logical person knew that there were exactly 100 brown and 100 blue, then, on the first night, they would hear the condition of the Guru that everyone with blue eyes could leave. That next day, they would walk around and count the eye colors of everyone. Once they reached 100 brown eyed persons, they would say.. I am obviously a blue eye, and leave the second night.

So, If I can't logically deduce my eye color, as it may be red, I cannot actually assume that I must be a brown eye or a blue eye. As stated, there could be 101 brown eyes. Because there's not a definite ratio of blue to brown from the logical thinker's point of view, Each of the blues could easily come to the assumption that they are a brown eye, or a red eye. They do not have the privilege of knowing the problem as you do, the solver.

So, the logical thinker, in his position can't deduce that he has red eyes, therefore cannot begin counting days when nobody else is leaving. In his mind, he only thinks I may have brown OR red eyes. Since he doesn't know the rules or the ratio, he will not waste his time counting the days that nobody leaves. It would be a waste of time from the get-go. It's more logical to drink coconut rum, swim, fish, catch some rays and test Gilligan Island Science.

So, the answer to the problem is 'They are deadlocked'. There is simply not enough information to accurately ascertain their own eye color. While you can mathematically deduce from the 4th wall (you can see everyone with blue and brown eyes and count them.) and create a mathematical model, they can not.

~DocNasty

[rrwoods]

While you can mathematically deduce from the 4th wall (you can see everyone with blue and brown eyes and count them.) and create a mathematical model, they can not.

Incomplete information does not make producing a mathematical model impossible. Since they are all perfect logicians (and everyone knows that everyone else is a perfect logician (and everyone knows ... )), before the Guru even speaks, they all have mathematical models of the system in which they don't know their own eye color (and they all have mathematical models of others' mathematical models (and they all have ...)). Hence the solution works with your "deadlock" being resolved on the 100th day as all the missing information in all the models is filled in.

[skullturf]

Also, I don't think there's any difference between brown eyes and red eyes in this puzzle. All that matters is that some people have blue eyes, and some people don't. It doesn't matter how many non-blue colors there are.

[rigwarl]

@DocNasty

They're only counting blue eyes, not brown (as you are stating in your post). Consider the situation with yourself (let's just say red eyes), 1 other blue eyed person, and 1 other brown eyed person.

[douglasm]

So, the logical thinker, in his position can't deduce that he has red eyes, therefore cannot begin counting days when nobody else is leaving.

Where did you get the idea that deducing your own eye color is necessary to start the counting process? Deducing eye color is an end result of the counting process, not a prerequisite for starting it.