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

[Xias]

Consider: We are blue-eyed, on an island with 101 blue-eyed people. Day 1, the guru makes their announcement that they can see a blue-eyed person. Then, later that afternoon, there is a second meeting that we don't know about, but all the other islanders go to, where the guru says they can see at least 2 blue-eyed people on the island. The blue-eyed people who made it to that second meeting will leave on night 100, and we will be left behind. Everything we see is consistent with us being a brown-eyed person on the island with 100 blue-eyed people and no second meeting... We can't tell the situations apart, so we can't deduce our eyes aren't blue.

I really like this. I didn't immediately see anything wrong with t1m's suggestion, but your argument makes sense. It's especially interesting when you realize that in the original puzzle, the islanders don't have to assume that no such additional meetings take place: if some number of meetings that are unknown to any combination of islanders take place that allow a subset of blue eyed islanders to figure out their eye color sooner, it immediately leaves the rest of the blue eyed islanders stuck on the island and there is no contradiction.

[dudiobugtron]

I think a secret 'second meeting' would be outside the spirit of the puzzle (specifically, "Everyone can see everyone else at all times", and more generally about there being no hidden tricks).

I think the puzzle would be fine if it's common knowledge that no one has access to any 'secret' relevant information.

Spoiler:

Edit: Also, I just found a nice way to think about the puzzle I hadn't considered before.
When I first read the puzzle it seemed wrong, but once I understood the bit about common knowledge, I could see that the puzzle was correct. I could see that they gained extra information each night, and why they therefore couldn't just leave early. But it didn't really sit right with me since there were so many levels of regression; I couldn't visualise it all at once.
I think that this way of thinking about the extra information they gain each night, however, makes it much clearer (to me, anyway) why they can't leave until night 100:

When the guru speaks, the extra information learned is that it is common knowledge that there is at least 1 blue eyed person.
When no one leaves on the first night, the extra information learned is that it is common knowledge that there are at least 2 blue eyed people.
When no one leaves on the second night, the extra information learned is that it is common knowledge that there are at least 3 blue eyed people.
...etc...
When no one leaves on the 98th night, the extra information learned is that it is common knowledge that there are at least 99 blue eyed people.
Therefore, when no one leaves on the 99th night, the extra information learned is that there are at least 100 blue eyed people. (And also that it's common knowledge - but that's not necessary at this stage!)

[Xias]

I think a secret 'second meeting' would be outside the spirit of the puzzle (specifically, "Everyone can see everyone else at all times", and more generally about there being no hidden trickses).

I think the puzzle would be fine if it's common knowledge that no one has access to any 'secret' relevant information.

That's the thing though, in the original puzzle, it doesn't need to be explicitly stated and known by the islanders that no such additional information is held by any of the other islanders. With t1m's wording, on the other hand, the islanders would have to know that. The secret meetings thing is just an example of how other islanders might have additional information.

It really makes the original puzzle that much more beautiful, to me at least.

[dudiobugtron]

I still think that being able to know secret relevant information makes the puzzle less interesting.

Also, I disagree that there is no information that could be introduced that would affect the logical deductions of the people in the original problem. Here are some examples of information that you have to assume is not allowed:
-Some islanders are red/blue colourblind.
-Some Islanders are wearing eye-colour-changing contact lenses.
-Anything else which suggests their perception of eye colour isn't always reliable.
-An islander's eye colour can change under certain circumstances.
-On day 99, the guru calls a secret meeting of 99 blueys and says "I can see 100 people with blue eyes". (This would lead the last remaining blue-eyed islander to deduce that his/her eyes are not blue.)
etc...

I understand that it is possible to draw a distinction between this information and the information that phlip says you can't assume doesn't exist, but to me both types go against the spirit of the puzzle.

[phlip]

It's certainly against the spirit of the puzzle for us as puzzle solvers to suggest they exist - that wouldn't be a satisfying solution to the puzzle. However, it's something that the islanders can't assume doesn't exist, because there's nothing in the puzzle that guarantees it, to their knowledge. The blanket "there's no crazy tricks" statement isn't in the "this is common knowledge" section, after all. This is what makes it different from the other things you suggested... if an islander is colourblind, then they still have to be keeping track of everyone's eye colour somehow, because the puzzle says they do. And this is common knowledge.

It's the same as the argument against the superrational solutions... Sure, we know all the blue-eyed people are symmetric, but they don't know that.

[dudiobugtron]

With that take, then, in the original puzzle, how do the islanders know that other islanders don't have access to extra information about their eye colour? Specifically, what happens in this situation:

-On day 99, the guru calls a secret meeting of 99 blueys and says "I can see 100 people with blue eyes". (This would lead the last remaining blue-eyed islander to deduce that his/her eyes are not blue.)

?

[phlip]

They don't. That's my point. But the standard solution doesn't rely on there not being additional information in play. That is, say I'm on the island and can see 99 blue-eyed people. I can reason that if my eyes are not blue, and there's no additional information going around, then the other blue-eyed islanders will leave on night 99. And if my eyes are not blue, and there is additional information out there, then they'll leave on night 99 or sooner (since information is additive). So when it comes to day 100 and they don't leave, I can deduce my eyes are blue either way.

On the other hand, in the alternative situation where there is additional information, and some blue-eyed people do leave early, then the chain breaks and any remaining blue-eyed people will be unable to deduce their eye colour.

[t1mm01994]

(This would lead the last remaining blue-eyed islander to deduce that his/her eyes are not blue.)

This is the part that is untrue. He would only deduce that if he knew no tricks happened, but he doesn't know that - it's false, too.

[dudiobugtron]

Ah, excellent. Thanks for setting me straight. What I like about this puzzle is that whenever you think you have a good objection to it, you actually don't. I'm beginning to share Xias' approval of the original puzzle.

[rmsgrey]

It's the same as the argument against the superrational solutions... Sure, we know all the blue-eyed people are symmetric, but they don't know that.

Well, they know the blue-eyed people are symmetric, and they know the brown-eyed people are symmetric, but they don't know which symmetric group they're in.

[Xias]

It's the same as the argument against the superrational solutions... Sure, we know all the blue-eyed people are symmetric, but they don't know that.

Well, they know the blue-eyed people are symmetric, and they know the brown-eyed people are symmetric, but they don't know which symmetric group they're in.

How do the islanders know the blue-eyed people are symmetric?

[rmsgrey]

It's the same as the argument against the superrational solutions... Sure, we know all the blue-eyed people are symmetric, but they don't know that.

Well, they know the blue-eyed people are symmetric, and they know the brown-eyed people are symmetric, but they don't know which symmetric group they're in.

How do the islanders know the blue-eyed people are symmetric?

"Symmetric" in the sense that all blue-eyed people are interchangeable when it comes to deductions about eye-colour. They know it for the same reason we do - that it's a logical consequence of the scenario's rules, which are known to them as well as to us.

[Xias]

It's the same as the argument against the superrational solutions... Sure, we know all the blue-eyed people are symmetric, but they don't know that.

Well, they know the blue-eyed people are symmetric, and they know the brown-eyed people are symmetric, but they don't know which symmetric group they're in.

How do the islanders know the blue-eyed people are symmetric?

"Symmetric" in the sense that all blue-eyed people are interchangeable when it comes to deductions about eye-colour. They know it for the same reason we do - that it's a logical consequence of the scenario's rules, which are known to them as well as to us.

All they know is that if a logical conclusion can be reached from the common knowledge, they will all reach it, but that's not exactly symmetry. Blue-eyed person A does not know that all of the other blue-eyed people have exactly the same knowledge, and there exists a possibility (for the islanders) any of the islanders might draw from additional resources in order to find their eye color sooner. So from A's perspective, he does not know that all of the blue-eyed people are symmetric. What he does know is that, since he sees 99 blue eyed islanders, the only possible reason they would take longer than 99 days to leave is if he has blue eyes. No other amount of additional, asymmetric funny business could change that.

The fact that all blue eyed islanders will come to any deduction about eye color simultaneously is known to us, but not to them; there is simply a point in time where a different deduction becomes impossible. At that point, all of the blue eyed islanders realize each others symmetry, but not at any moment before.

[rmsgrey]

The fact that all blue eyed islanders will come to any deduction about eye color simultaneously is known to us, but not to them; there is simply a point in time where a different deduction becomes impossible. At that point, all of the blue eyed islanders realize each others symmetry, but not at any moment before.

Okay, yes, if it's not known to the islanders that the only "uncommon" knowledge is which eye colour each person has (and anything derived from that), then we know something the islanders don't, and can deduce symmetry when they can't. I'd have to reread the specific problem statement to confirm that that's the case.

[Paragon99]

If there were 5 brown eyed people, and 10 blue eyed people and the guru said... I see someone with blue eyes... then on the 11th day the 10 blue eyed people leave... still the original question so it works the same.

What if instead the Guru said, I see someone with blue eyes, AND I see someone with brown eyes...
So... the person with brown eyes sees 4 people with brown eyes and knows there is a maximium of 5 brown eyed people and they see 10 people with blue eyes with a max of 11
a person with blue eyes sees 5 people with brown eyes and knows there is a maximium of 6 brown eyed people and they see 9 people with blue eyes with a max of 10.

Morning 1) No one left so everyone knows that every one sees a brown eyed person and blue eyed.
Morning 2) No one left so everyone knows that everyone sees 2 brown eyed and blue eyed people
Morning 3) No one left so everyone knows that everyone sees 3 brown eyed and blue eyed people
Morning 4) No one left so everyone knows that everyone sees 4 brown eyed and blue eyed people
Morning 5) No one left so everyone knows that at least some people see 5 brown eyed and blue eyed people, but the brown eyed people only see 4 brown eyed people so they know that they must be the fifth
Morning 6) Everyone with brown eyes is gone. and all blue eyed people remain. and everyone knows that everyone remaining sees 6 Blue eyed people
.
.
.
Morning 10) No one has left yet so they know the max of 10 blue eyed people has been reached
Morning 11) Everyone with blue eyes leaves.

Is the above still correct?

Now, what if the number of blue eyed and brown eyed people where equal (10 and 10) and the guru says I see someone with blue eyes AND I see someone with brown eyes... would anyone be able to leave?

[rmsgrey]

Now, what if the number of blue eyed and brown eyed people where equal (10 and 10) and the guru says I see someone with blue eyes AND I see someone with brown eyes... would anyone be able to leave?

Yes.

A blue-eyed islander knows there are three possibilities:

10 brown and 10 blue including him
9 blue and 11 brown including him
10 brown, 9 blue and 1 other (himself)

In either of the possibilities with only 9 blues, the blues will all leave on the 9th ferry, so, when they don't, our sample islander knows he has blue eyes. The same reasoning applies for any brown-eyed islanders.


The fact that any islander whose opinion we care about has eyes of one of the colours being counted means that it's impossible to create a distribution of eye colours where the symmetry keeps the islanders from deducing their eye colour - any two islanders with different eye colours will disagree on their false hypothetical populations by 1-2, breaking the symmetry.

Admittedly, it's not clear what would happen with a case of heterochromia.

[ewlusky]

I know this is way late and nobody will probably read this but I just stumbled upon this problem today, and it took me about 20 minutes to solve it and then I just suddenly thought about how absolutely sad every single brown eyed person would be when all 100 blue eyed people got up and left. Each one of them sees 100 blue eyed people and every day closer to day 101 they anticipate that they might also have blue eyes and will finally be able to leave the island until bam! on day 100 all the blue eyed people leave and they realize that they are not among them, but that's ALL they know, they know they are NOT blue eyed, but still have no idea as to their actual eye color. What a brutal let down.

[Gwydion]

I know this is way late and nobody will probably read this but I just stumbled upon this problem today, and it took me about 20 minutes to solve it and then I just suddenly thought about how absolutely sad every single brown eyed person would be when all 100 blue eyed people got up and left. Each one of them sees 100 blue eyed people and every day closer to day 101 they anticipate that they might also have blue eyes and will finally be able to leave the island until bam! on day 100 all the blue eyed people leave and they realize that they are not among them, but that's ALL they know, they know they are NOT blue eyed, but still have no idea as to their actual eye color. What a brutal let down.

Alternatively, what a relief when the brown-eyed people all find out together that they get to stay on the island, after 100 days of mounting dread that they might have blue eyes and be forced to leave. Pretty awesome that their eye color remains hidden.

[dudiobugtron]

It's part of the puzzle that they don't care whether or not they stay on the island. Apparently, being perfect logicians makes them immune to other feelings!

[phlip]

It's part of the puzzle that they don't care whether or not they stay on the island.

Eh, kinda... I'd put it more that whether they care or not isn't part of the puzzle at all... the puzzle just says they will leave once they can figure out their eye colour... it doesn't say why, doesn't say whether it's what the islanders want or not, just asserts that it will happen.

[Veneficus]

I understand the logic, but there is one point where I believe it to fall apart:

Since they do not have any means of communication, they would need to all leave AT THE EXACT SAME MOMENT. As long as no-one moves, no other persons can make any deduction. And no-one WILL move, because there are more than 1 blue eyed people on the island, which they all knew already. So no-one ever leaves the island, because they will never know if there are 99 or 100 blue-eyed people.

[Xias]

I understand the logic, but there is one point where I believe it to fall apart:

Since they do not have any means of communication, they would need to all leave AT THE EXACT SAME MOMENT.

Nope. As soon as the 99th night comes and nobody leaves, all 100 blue eyed islanders know that they have blue eyes. They aren't waiting for the rest to get up and leave on day 100. They just get up and leave.

As long as no-one moves, no other persons can make any deduction. And no-one WILL move, because there are more than 1 blue eyed people on the island, which they all knew already.

"which they all knew already" doesn't matter, because it wasn't common knowledge. This has been discussed at length in this thread. If you and I were the only two blue-eyed people, then I would know there was at least one blue eyed person, but I wouldn't know that you knew it until the Guru spoke. If we were among the only three blue-eyed people, then I would know that you knew that there was at least one blue eyed person, but I wouldn't know that you know that Steve knows it. Etc.

[petulantpro]

What's wrong with this logic?

Scenario:
100 blue, 900 brown. I'm blue

-----Day 1-----

Logic:
I assume the 99 I see all see 98 and think it's a 98 situation where the 98 all think it's a 97 situation.

My expected outcome:
I therefore expect the 99 to each assume it isn't them and wait a day.

Actual outcome:
1 day is passed as every blue concluded this.

-----Day 2-----

Logic:
I assume that each 99 waited a day since they each thought it was a 98 looking at 97 situation.

My expected outcome:
I expect the 99 to realize that each of the 98 they see also saw 98 and leave.

Actual outcome:
1 more day is passed since every blue concluded that.

-----Day 3-----

Logic:
I assume that that each 99 waited a day because they each saw 99 and thought it was a 99 looking at a 98 situation now. That means there are 100.

My expected outcome:
I realize there are 100 and I see 99. Therefore I'll leave the island.

Actual outcome:
I leave the island

-----Conclusion-----
Solution is possible but in a max of 3 days in any situation where N is greater than 3?

[Krealr]

What's wrong with this logic?

<Snip>

-----Conclusion-----
Solution is possible but in a max of 3 days in any situation where N is greater than 3?

See number three on the typical objections page. http://forums.xkcd.com/viewtopic.php?f=3&t=80149

[firechicago]

Your contention is that for any number of blue eyed people, all of them should deduce their eye color and leave on night 3.

So tell me, I'm living on the island. I see 99 blue eyed people. It is day 3 and no one left on night 1 or night 2.

What color are my eyes?

[petulantpro]

Your contention is that for any number of blue eyed people, all of them should deduce their eye color and leave on night 3.

So tell me, I'm living on the island. I see 99 blue eyed people. It is day 3 and no one left on night 1 or night 2.

What color are my eyes?

Your eyes would be blue because if they were brown, everyone would've left on day 2 per my logic. Making it to day 3 made you realize that it wasn't a 98 looking at a 97 situation where the 97 think it's the others.

Maybe I'm missing something, but I don't see where my logic goes wrong in my solution. If someone could point out what assumption I'm making which isn't correct, that might help me wrap my head around it.

See number three on the typical objections page.

Sorry, but I disagree with that. I don't see why you have to follow this:

"Every time you add the word "knows" to a statement of the form "A knows that B knows that… D sees at least N blue-eyed people", you have to subtract 1 from N."

I see 99. I know that each one sees 98. How is that not true?

[firechicago]

Your eyes would be blue because if they were brown, everyone would've left on day 2 per my logic. Making it to day 3 made you realize that it wasn't a 98 looking at a 97 situation where the 97 think it's the others.

Maybe I'm missing something, but I don't see where my logic goes wrong in my solution. If someone could point out what assumption I'm making which isn't correct, that might help me wrap my head around it.

So if there are 99 then they all leave on day 2 and if there are 97 they all leave on day 1 and if there are 96 they all leave on day 0...

Do you see the absurdity of your position?

(More rigorously, if your solution provides that any number of people will leave on day 3, it is literally impossible to tell how many blue eyed people there are on day 3, because we expect to see the exact same behavior no matter what number of blue eyed people there are.)

More specifically, here's the step where you go wrong:

Logic:
I assume the 99 I see all see 98 and think it's a 98 situation where the 98 all think it's a 97 situation.

This step is cut way too short, because if the 98 all thing it's a 97 situation, then they need to consider the possibility that the 97 think it's a 96 situation, which means that they need to consider the 95 situation and so on, all the way down to one. Read the objections thread Krealr linked to, it covers this much more completely.

[petulantpro]

Logic:
I assume the 99 I see all see 98 and think it's a 98 situation where the 98 all think it's a 97 situation.

This step is cut way too short, because if the 98 all thing it's a 97 situation, then they need to consider the possibility that the 97 think it's a 96 situation, which means that they need to consider the 95 situation and so on, all the way down to one. Read the objections thread Krealr linked to, it covers this much more completely.

Sorry, but I disagree with that. The point 3 which Krealr refers to has a section called "Edit 2" which I don't see as being true, despite being proposed as a counter argument to my issue:

"EDIT 2: Here may be a simpler way to put it, a point raised by many dealing with this problem: If you think the blue-eyed people can nonverbally agree on some sort of common minimum which is greater than zero, than surely the browns should agree to the same minimum, or else it's not really common to the islanders. But how? Suppose each blue thought "I see 99 blues. 99 minus 2 is 97, so 97 is the absolute common minimum to which we all agree." In that case, a brown-eyed person would go "I see 100 blues. 100 minus 2 is 98, so 98 is the absolute common minimum". If a brown instead came to conclude that the minimum is 97, that means he went one step further than a blue would. Why would he? See, this is the (initially) surprising result of the existence of a one-person difference between two people's counts of eye color, all thanks to the commonly-known fact that no one knows the color of her own eyes."

The "known to all minimum" is from a blues perspective. Notice that a brown's logical "known to all minimum" is 1 higher (logically) than a blues "known to all minimum" (with 100 blue, a brown's "known to all minimum" would be 99, a blue's would be 98). This would mean that browns would lag a day behind which is why they wouldn't leave with the blues.

"Everyone knows that everyone else will never see a 96 situation." What is wrong with this statement?

[rmsgrey]

Logic:
I assume the 99 I see all see 98 and think it's a 98 situation where the 98 all think it's a 97 situation.

This step is cut way too short, because if the 98 all thing it's a 97 situation, then they need to consider the possibility that the 97 think it's a 96 situation, which means that they need to consider the 95 situation and so on, all the way down to one. Read the objections thread Krealr linked to, it covers this much more completely.

Sorry, but I disagree with that. The point 3 which Krealr refers to has a section called "Edit 2" which I don't see as being true, despite being proposed as a counter argument to my issue:

"EDIT 2: Here may be a simpler way to put it, a point raised by many dealing with this problem: If you think the blue-eyed people can nonverbally agree on some sort of common minimum which is greater than zero, than surely the browns should agree to the same minimum, or else it's not really common to the islanders. But how? Suppose each blue thought "I see 99 blues. 99 minus 2 is 97, so 97 is the absolute common minimum to which we all agree." In that case, a brown-eyed person would go "I see 100 blues. 100 minus 2 is 98, so 98 is the absolute common minimum". If a brown instead came to conclude that the minimum is 97, that means he went one step further than a blue would. Why would he? See, this is the (initially) surprising result of the existence of a one-person difference between two people's counts of eye color, all thanks to the commonly-known fact that no one knows the color of her own eyes."

The "known to all minimum" is from a blues perspective. Notice that a brown's logical "known to all minimum" is 1 higher (logically) than a blues "known to all minimum" (with 100 blue, a brown's "known to all minimum" would be 98, a blue's would be 97). This would mean that browns would lag a day behind which is why they wouldn't leave with the blues.

"Everyone knows that everyone else will never see a 96 situation." What is wrong with this statement?

So you're saying that if I'm on the island, see 99 people with blue eyes, I should immediately think:

• Ah, either there are only 99 people with blue eyes, all of whom will leave on day 2, or there are 100, including me, and we should leave on day 3. Why? Because if I have brown eyes, then all the 99 people with blue eyes will look around, see 98 people with blue eyes, and think
  • Ah, either there are only 98 people with blue eyes, all of whom will leave on day 1, or there are 99, including me, and we should leave on day 2. Why? Because if I have brown eyes, then all the 98 people with blue eyes will look around, see 97 people with blue eyes, and think
    • Ah, either there are only 97 people with blue eyes, all of whom have already left yesterday, or there are 98 including me and we should all leave on day 1. Since 97 people didn't leave yesterday, I must have blue eyes.

That doesn't seem quite right somehow - how would the hypothetical 97 know to leave before anyone said anything?


Look at it another way:

Applying your solution to the situation where there are 99 people with blue eyes to start with, and following the same reasoning, I get that they will all leave on day 3, so if I'm a brown-eyed man on an island with 99 blue-eyed people, I expect them to leave on day 3, while if I were a blue-eyed man, I would expect them to leave on day 2? Wait, when I see 99 blue-eyed people, how do I know whether we're agreeing that 97 is the common minimum, and the others will all leave on day 3, or 98 is the common minimum, so I should expect them to leave on day 2 and then leave with them on day 3?

***

The thing is, while, when I see 99 blue-eyed people, I know that everyone on the island knows that there are at least 98 blue-eyed people, I don't know whether everyone else on the island also knows that - the strongest statement I know that everyone knows that everyone knows is that there are at least 97 blue-eyed people - and I don't know that everyone knows that too either. What I know about what everyone knows and what I know other people know about what everyone knows don't catch up until we get to people's knowledge about there being at least 1 blue-eyed person, which everyone knows, and knows that everyone knows, and knows that everyone knows that everyone knows and...

So there's nothing wrong with saying "Everyone knows that everyone else will never see a 96 situation" but you also need to be able to say that "Everyone knows that everyone else knows that everyone else knows that everyone else will never see a 96 situation" which, alas, is not true...

[Xias]

petulantpro, if there were 101 blue-eyed people, what day would they leave if they followed your logic?

[Trebla]

I'll detail the specific example and spoiler it in case you'd still like to come to the conclusion on your own.

Spoiler:

We'll go with your scenario. 100 blue eyes.
BLUE is a person with blue eyes and sees 99 blue eyes.
BROWN is a person with brown eyes and sees 100 blue eyes.

Day 1:
BLUE assumes the 99 all see 98 blue eyes, all of whom think it's a 97 solution. He expects the 99 to assume it isn't them and wait a day.
BROWN assumes the 100 all see 99 blue eyes, all of whom think it's a 98 solution. He expects the 100 to assume it isn't them and wait a day.

Day 2:
BLUE assumes that each 99 waited a day since they thought it was 98 looking at 97. He expects the 99 to realize that each of the 98 also saw 98 and will leave.
BROWN assumes that each 100 waited a day since they thought it was 99 looking at 98. He expects the 100 to realize that each of the 99 also saw 99 and will leave.

Day 3:
BLUE assumes that each 99 waited a day because they each saw 99 and thought it was 99 looking at a 98 solution. That means there are 100.
BROWN assumes that each 100 waited a day because they each saw 100 and thought it was 100 looking at a 99 solution. That means there are 101.

Actual outcome.
BLUE leaves the island since he concluded there are 100 blue eyes, and he only saw 99.
BROWN leaves the island since he concluded there are 101 blue eyes, and he only saw 100.

Edit: Fixed a ridiculous number of typos

[Dontget]

I think my favourite thing about this logic puzzle is that, in spite of my best logical efforts, I had to actually attempt the puzzle in order to convince myself. It is of incredible importance that each brown-eyed person would be seeing one more blue-eyed person than any given blue-eyed person would be seeing. At one person, the solution is obvious. The guru says she sees a blue-eyed person, and the blue-eyed person sees no blue eyes, so it must be him. However, even to solve for two blue-eyed people, the solution begins to rely on the brown-eyed people. A blue-eyed person would see one blue-eyed person, and thus not leave on the first day. Seeing no other blue-eyed people, and seeing that the one blue-eyed person that is not him had not left on the first day, he will conclude that there must be two blue-eyed people, and he must be one of them, because if there were only one blue-eyed person, he would certainly have left on the first day. However, this only works in contrast to what the brown-eyed people are seeing. If their logic weren't perfect, and the two blue-eyed people didn't leave on the second day for some reason, then on the third day, every brown-eyed person would have to believe that he had blue-eyes, and then attempt to leave. Thus, logically, the only thing keeping a person with blue eyes from thinking he has brown eyes is the fact that the other people with blue-eyes did not leave on the first day they possibly could have, otherwise. And, on the other hand, a person with brown eyes will never be sure he doesn't have blue eyes until all of the blue-eyed people leave. The only thing that causes the situation not to go awry is that all of the blue-eyed people leave one day before [a person who has brown eyes but is under the assumption that he has blue eyes] would attempt to leave.

This is of particular importance to me because, while I understood the conclusion that was drawn, it took a lot of effort to convince myself of the reason that every brown-eyed person wouldn't think he had blue eyes. And he would -- only one day too late.

[Lunch Meat]

I've been thinking about this puzzle and think I've come up with a different way of explaining the solution--at least I don't remember seeing it before. Most of the solutions I've seen start from the bottom--proving that one blue-eyed person will leave on Day 1, therefore two blue-eyed people will leave on Day 2, therefore three on 3, etc.

I started thinking about it from the top down, like so:
It's intuitively clear that if the number of blue-eyed people indicated by the guru, X, is equal to the number of blue-eyed people on the island, Y, then they will all leave on Day 1.
Suppose there are 100 blue-eyed people and the guru says she can see 100 blue-eyed people, they will all leave that night.
Suppose there are 99 blue-eyed people and the guru says she can see 99 blue-eyed people, they will all leave that night.
And so on and so on all the way down.

It's also pretty intuitive that if X=Y-1, all X people will leave on Day 2.
Suppose there are 100 blue-eyed people and the guru says she can see 99 blue-eyed people, they will all leave the next night.
Suppose there are 99 blue-eyed people and the guru says she can see 98 blue-eyed people, they will all leave the next night.
Suppose there are 98 blue-eyed people and the guru says she can see 97 blue-eyed people, they will all leave the next night.
And so on and so on.

It's where X=Y-2 that things start becoming not intuitively clear. If there are 100 blue-eyed people and the guru says she can see 98 blue-eyed people, it's not immediately obvious what information is added. As the common objection goes, everyone already knew there were 98 blue-eyed people. But a random blue-eyed person (A) will not know they're in a situation where Y=100; they will suppose that Y=99. And therefore they will assume all the blue-eyed people will leave on Day 2, and when that doesn't happen they will know that Y=100. Therefore we can determine that if X=Y-2, all X people will leave on Day 3.

So what if X=97 and Y=100? A will suppose that Y=99 and therefore all blue-eyed people will leave on Day 3. This is because A₁, the random blue-eyed person in the supposed Y=99 situation, will be supposing A is not-blue-eyed (A₁, existing in A's imagination, cannot have any information that A doesn't have), that Y=98 and therefore all blue-eyed people will leave on Day 2. A knows that no one will leave on Day 2, but A₁ does not know that because A₁ does not know their own eye color. A needs to wait for A₁ to determine that Y isn't 98 before A can use A₁'s lack of action to determine that Y isn't 99. When no one leaves on Day 3, A will know that Y=100 and all will leave on Day 4.

When X=96, A will suppose that Y=99, A₁ will suppose that Y=98, and A₂ will suppose that Y=97 (A₂ cannot have any information about A or A₁). A₂ will expect all blue-eyed people to leave on Day 2, and A₁ will expect them to leave on Day 3. A knows that no one will leave on Day 2 or 3, but needs to wait for A₂ to determine that Y isn't 97, so that A₁ can determine Y isn't 98. When no one leaves on Day 4, A will know that Y=100 and all will leave on Day 5.

This isn't actually a new explanation, just another way of looking at nested hypotheticals. We know that when Y=100, A will assume Y=99. A knows that if Y=99, A₁ will assume Y=98. A₁ knows that if Y=98, A₂ will assume Y=97. A₂ knows that if Y=97, A₃ will assume Y=96. Yes, A already knows that Y isn't 98, 97, or 96, and that if X=95, no one will be leaving on Days 2, 3, or 4. A₁ knows that Y isn't 97 or 96 and no one will be leaving on Days 2 or 3. A₂ knows that Y isn't 96 and no one will be leaving on Day 2. But A has to wait for A₁ to decide whether to leave on Day 5, which means A has to wait for A₂ to decide whether to leave on Day 4, which means A has to wait for A₃ to decide whether to leave on Day 3. Any solution that skips one of these steps will boil down to something contradicting our rule that if X=Y, all blue-eyed people will leave on Day 1.

[OP Tipping]

There is a version of this that just appeared here.

http://io9.com/can-you-solve-the-hardes ... 1642492269

An old solution is posted here.
https://www.physics.harvard.edu/uploads ... k/sol2.pdf

It is different in that there are 100 dragons, all green eyed. They turn into a bird instead of leaving the island.

Thing is, I am not buying the solution. I think that the induction terminates, short-circuits, after two iterations.

Before the Guru speaks, each dragon knows there are either 99 or 100 GED.

Each dragon therefore holds two possibilities in mind:
A)if there are 100 GED, Then all the other dragons also know there are 99 to 100 GED.
B)if there are 99 GED, then all the other dragons know there are 98 to 99 GED.

Unless they are the dumbest dragons evah, they already thought of this before the Guru speaks. No dragon thinks there are fewer than 99 GED, no dragon thinks any other dragon thinks there are fewer than 98 GED... and no dragon thinks that any other dragon thinks any other dragon thinks there are fewer than 98 GED, and no dragon thinks any other dragon thinks any other dragon thinks any other dragon thinks any other dragon thinks that there are fewer than 98 GED etc. They need never consider for a second that there's a dragon on the island who thinks there are fewer than 98 GED Or that any other dragon who'd think so etc. It's transparently obvious that all dragons know all dragons know there are at least 98 GED.

So the guru makes his announcement and the dragons should all shrug and say "well, duh".

[HipsterPuff]

Allow me to point out a single flaw in the argument:

Say I'm a dragon on the island, there's 99 green-eyed dragons, and I have black eyes. From my perspective, we might be in the 100 or the 99 dragons case.
Now, let's look at what others know: I know every other dragon knows there's at least 98 dragons with green eyes.
I know every other dragon knows every other dragon knows there's at least 97 dragons with green eyes.

These last two statements are independent of my own eye colour - if I had green eyes, the same statement would still be true, which would mean that in the 100 dragons case I would not be sure whether all dragons know all dragons know there's at least 98 dragons.

[Gwydion]

Each dragon therefore holds two possibilities in mind:
A)if there are 100 GED, Then all the other dragons also know there are 99 to 100 GED.
B)if there are 99 GED, then all the other dragons know there are 98 to 99 GED.

Unless they are the dumbest dragons evah, they already thought of this before the Guru speaks. No dragon thinks there are fewer than 99 GED, no dragon thinks any other dragon thinks there are fewer than 98 GED... and no dragon thinks that any other dragon thinks any other dragon thinks there are fewer than 98 GED, and no dragon thinks any other dragon thinks any other dragon thinks any other dragon thinks any other dragon thinks that there are fewer than 98 GED etc. They need never consider for a second that there's a dragon on the island who thinks there are fewer than 98 GED Or that any other dragon who'd think so etc. It's transparently obvious that all dragons know all dragons know there are at least 98 GED.

The trouble with trying to put yourself in someone else's mindset is the nagging thought that you already know better. In this case, it's not enough to put yourself into the mind of the next dragon, but the next one after that and the next one after that...

It is transparently obvious, as you say, that all dragons know that all dragons know that there are at least 98 GED. This is because all dragons know that there are at least 99 GED, and none of them know their own eye color. But is it fair to say that all dragons know that all dragons know that all dragons know that there are 98 GED? Let's name the dragons for simplicity. Dragon 1 knows that there are 99 GED. 1 knows that 2 sees at least 98 GED. But does 1 know that 2 knows *for certain* that 3 can also see 98 GED? We, as outside observers, know that 3 can in fact see 99 GED, but among these are 1 and 2, who in this nested hypothetical circumstance don't know their own eye color. So 3 can see 99, and 2 knows that 3 can see 98, but 1 only knows that 2 knows that 3 can see 97.

This argument can be extended through all 100 dragons, such that #100 does not in fact know, before anyone speaks, that 99 knows that 98 knows... that 2 knows that 1 can see any GED. However, after the person speaks, this last situation is known to be false - every dragon knows that at least one GED exists, and everyone knows that all 100 dragons heard this, and knows that they all know that everyone heard this ad infinitum. The existence of GED has become common knowledge, which it technically was not before, and this leads to the stepwise collapse of these hypothetical scenarios which we can now be certain are false.

[kokevi]

Sorry, edit posted below

[kokevi]

This argument can be extended through all 100 dragons, such that #100 does not in fact know, before anyone speaks, that 99 knows that 98 knows... that 2 knows that 1 can see any GED. However, after the person speaks, this last situation is known to be false - every dragon knows that at least one GED exists, and everyone knows that all 100 dragons heard this, and knows that they all know that everyone heard this ad infinitum. The existence of GED has become common knowledge, which it technically was not before, and this leads to the stepwise collapse of these hypothetical scenarios which we can now be certain are false.

The argument here is that the fact that there are Green eyes is mutual knowledge, not common knowledge. For it to be common knowledge all dragons must know there are green eyes (1), they must know the other dragons know that there are green eyes (2), and they must know the other dragons know they know (3).

(1) is satisfied as all dragons can see another dragon with green eyes.
(2) is satisfied as all the other dragons must be able to see at least 98 dragons with green eyes
(3) this is the tricky bit where it seems that the regression must start as with the next levels seeing 97, 96 etc. But in fact it is not necessary to have a chain to have common knowledge. It will work with a different mapping. This is my reasoning

Look at a specific dragon and what the population knows about it. #50 has green eyes. All the other dragons know #50 has green eyes. All the other dragons know the other dragons know etc, as all can see and be seen to see. Therefore for the population excluding #50, it is common knowledge that #50 has green eyes. It is not common knowledge for the whole, as #50 doesn't know. Repeat this for all the dragons and it is clear that while it is not common knowledge which dragons have green eyes, it is that at least one has green eyes. This works for any population greater than 2.

The riddle seems to be derived from the proof that for a population with X number having a trait it will take X days to be able to determine if you have the trait. And this is still the case here that it will take 100 days to determine that there are 100 GED, but there is no starting point to count from, so as a riddle it is relying on something provide that starting point.

[rmsgrey]

The argument here is that the fact that there are Green eyes is mutual knowledge, not common knowledge. For it to be common knowledge all dragons must know there are green eyes (1), they must know the other dragons know that there are green eyes (2), and they must know the other dragons know they know (3).

By the standard definition of common knowledge in logic, you need the infinite regress, or some equivalent condition (such as self-reference). Before the visitor says anything, all three of your conditions are met, but the knowledge is still only 99 levels deep - everyone knows₁ that everyone knows₂ that everyone knows₃ that ... that everyone knows₉₉ that there is at least one green-eyed dragon, but the green-eyed dragons don't know that - that's the crucial information that kicks everything off...

[chettski]

A few folks here have nailed it (especially OP Tipping), but most are missing the forest for the trees. Sure, you can work out the logic for n=1, n=2, and extend to n=100. But there's a clear fallacy here, in that the visitor/guru gives non-common information only in the case of n=1 or 2, but not 3 or higher. The entire system breaks down if the visitor/guru gives already known information. There is no "starting the clock" when he/she states previously known (and obvious) information!

Someone (I forget who) correctly observed that this is a faulty logic problem. I believe the true logic problem lies in recognizing the fallacy of the initial "logic problem," which most miss, since they're wrapped around extending n from 3 through 100. This reminds me of Marilyn Vos Savant (and a legion of mathematics professors and statisticians... including my late grandfather) getting the Monty Hall problem spectacularly wrong. The key in that problem (which most miss) is that the host gives new information 2/3rds of the time, leading to the "better odds if you switch."

The correct wording of a solvable version of the blue-eyed puzzle must have the "discovery" of everyone else's eye color on day one, such as dragons/islanders blindfolded at birth, then removing the blindfolds all at once. Only then will you have the magic happen on day 100. As it stands, it's unsolvable.