Blue eyes riddle: a counter-argument to accepted solution

Question

I would like help understanding my flawed logic in my following reasoning:

The Blue-eyes Riddle is commonly expressed as

A group of people with assorted eye colors live on an island. They are all perfect logicians -- if a conclusion can be logically deduced, they will do it instantly. No one knows the color of their eyes. Every night at midnight, a ferry stops at the island. Any islanders who have figured out the color of their own eyes then leave the island, and the rest stay. 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. Everyone on the island knows all the rules in this paragraph.

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.

The Guru is allowed to speak once (let's say at noon), on one day in all their endless years on the island. Standing before the islanders, she says the following:

"I can see someone who has blue eyes."

Who leaves the island, and on what night?

There are no mirrors or reflecting surfaces, nothing dumb. It is not a trick question, and the answer is logical. It doesn't depend on tricky wording or anyone lying or guessing, and it doesn't involve people doing something silly like creating a sign language or doing genetics. The Guru is not making eye contact with anyone in particular; she's simply saying "I count at least one blue-eyed person on this island who isn't me."

And lastly, the answer is not "no one leaves."

The generally accepted solution states that all the blue-eyed people leave on the 100th day by the inductive reasoning of

	A	B	C	D
What A sees	?	Blue	Blue	Blue
What A knows B sees	?	?	Blue	Blue
What A knows B knows C sees	?	?	?	Blue
What A knows B knows C knows D sees	?	?	?	?

Image version of table 1

and hinges on the idea that someone could hypothetically think someone else does not know there are blue-eyed people on the island.

However, this does not account for parallel induction stated as

	A	B	C	D
What A knows B sees	?	?	Blue	Blue
What A knows C sees	?	Blue	?	Blue
What A knows D sees	?	Blue	Blue	?

Image version of table 2

which when combined with the sequential induction collapses to

A knows ABCD knows ABCD knows >0 blue eyes

This combined induction covers all purely sequential inductions past k=4 blue eyed peoples. Therefore, I propose the following proof:

Theorem 0. If it can be proven that everybody knows that no one thinks there are no blue-eyed people then the oracle does not provide extra information and no one leaves the island

Theorem 1. If you see 1 blue-eyed person, you can prove that there are >0 blue-eyed people

Theorem 2. If you see 2 blue-eyed people, you can prove that everyone can prove there are >0 blue-eyed people

Theorem 3. If you see 3 blue-eyed people, you can prove that everyone can prove that everyone can prove there are >0 blue-eyed people

In summary, the state of "What A knows B knows C knows D sees there are 0 blue-eyed people" is not possible given that "ABCD knows ABCD knows there are >0 blue-eyed people" and only possible states should be taken into consideration.

***EDIT:

Great answers by everyone who have commented or answered. They are a very good explanation of the logic to arrive to the general solution. I, however, am failing to grasp why the fact that everyone knows that blue-eyes are directly observable does not provide any information to anybody. There seems to me to be a contradiction that everyone can observe something (and everyone know it can be observed) and still believing that somehow someone may not be able to observe it.

Answer 1

Say I'm one of the residents of this island, and the Guru hasn't shown up yet. I'm a perfect logician, like all the rest of the residents... but I'm very forgetful. So, to help me remember things, I make little scale models of the island in my hut!

Whenever I'm unsure of something, I make two models of the island, and then see how the other perfect logicians would react in either case. And if anything is inconsistent with the information I know, I destroy the inaccurate model.

So what happens when the Guru arrives?

Of course, nobody does anything today in either of those situations. But I still haven't tallied up all the information I know! I happen to know that my neighbor also makes these kinds of models. And she doesn't know her own eye color, so she needs to make two of them as well. So those will naturally end up in my own scale model of the village.

In fact, these models have become a trend recently - the whole island's doing it! Of course, this means every model actually has sixteen more models inside it. (It takes a while to make, but there's not much else for us to do on this island.)

Here's a schematic zooming in on my model. Each time I zoom in on a person, they have two copies of the model they're in -- one where they have non-blue eyes, and one where they have blue eyes.

And nothing here is a hypothetical that everyone knows is wrong. This entire project is just me building two models of what exists on the island: it's either the left one or the right one. I don't know which it is, but those are the only two options I'm considering: five blue-eyed islanders, or six.

---

So I just finished building the two possibilities. Each has a bunch of other copies of the island inside it. (They get infinitely small, in fact! I have very steady hands.) And if my left model is ever smashed, I know I have blue eyes, so I must immediately leave the island.

...Oh right, the Guru said something, didn't they? Something about blue? Right, at least one person has blue eyes.

Well, it's time for me to start making my deductions. Which, of course, I do by playing out scenarios in my models. And of course, in those scenarios, people are playing out other scenarios...

(I take inspiration from the true masters of the art of rigorous logical deduction.)

Since I simulate the others with perfect accuracy, and they simulate other people with perfect accuracy as well, and so on, any model where everyone has brown eyes will be smashed by its owner.

When I'm pretending to be Alice, who is pretending to be Bob, who is pretending to be Charlie, who is pretending to be Donna, who is pretending to be Eve... this pretend-Eve will smash her model. This is the Guru's influence: she forces every single all-brown model to be smashed. And in my many, many simulations, all of the all-brown models must be smashed.

---

And now the chain reaction starts. The first day passes, and nobody has left. I go simulate the models, adding in this new information... and more impossible models occur. The "pretend-Donna" notices that Eve didn't leave that night, and so she smashes her left model.

Of course, I knew the entire time that nobody would leave on day 1. But I can't include all of my information in these pretend worlds. If I smash a model early, I would be giving information to the owner of that model that they wouldn't really have. And then my model wouldn't be accurate, and I can't have that!

And this continues on and on, until the moment of truth for me.

Will my neighbor leave the island? Or will they stay, forcing me to smash my own left model and leave the following night? I have no choice but to wait and watch...

---

Conclusion

The key to this puzzle is that everyone on the island is a perfect logician, and this is common knowledge. This means that, either through scale models or just by thinking about it, they can simulate other versions of the puzzle perfectly. They have two copies of the island in their heads, that act just as the original problem, but with different numbers of blue eyes.

And each of those residents of those islands has two versions of the island in their heads as well... The Guru gives information to not just the islanders, but to the entire islands in their heads, and the entire islands in their heads... until the islanders many layers down can finally act on that information, destroy one of their simulations, and leave the island.

Answer 2

Your "parallel induction" is already happening in the generally accepted solution

When the solution says "A considers that B considers that ...", B, C, and so on are all arbitrary people. So it does indeed extend to "A knows that everybody knows that...". However, you seem to be failing to take some uncertainty into account.

What new information does the Oracle provide?

What I find helpful is to consider the situation from the point of view of someone who does not have blue eyes. Let's consider your theorem 2 with that scenario:

You, as a person with brown eyes, see 2 blue-eyed people. So yes, you do know that everyone knows that at least one person has blue eyes. However, unknown to you, both of those blue-eyed people only see a single blue-eyed person so they do not know if anyone else sees someone with blue eyes. Notice the asymmetry between what you know and what the blue-eyed people know.

At this point you know that everyone sees at least one person with blue eyes. However, you do not know if they see one person, or two. If you have blue eyes (false in this scenario), they see two people with blue eyes and are making the same considerations you are. If you do not have blue eyes (true here), they see only one person with blue eyes. One of the scenarios they are considering is where the one person with blue eyes that they see does not see anyone else with blue eyes.

As soon as the oracle makes the announcement, you now know something new - nobody could possibly believe (or believe someone else believes, etc.) that nobody has blue eyes. When nobody leaves on the first night, you now know something else new - nobody could possibly believe that only one person has blue eyes.

This is the point at which the two people with blue eyes determine their eye color. Because there cannot be only one person with blue eyes, they each realize they must be the second person with blue eyes.

If you go through the logic for three people with blue eyes, you'll see something similar. It goes from knowing that at least one person has blue eyes, to knowing at least two people have blue eyes, to knowing that three people have blue eyes.

Instead of focusing on what people know, focus on what they *don't* know

If there are 4 people with blue eyes (A through D), then A knows that everybody sees at least one person with blue eyes, and that everybody knows that everybody sees at least one person with blue eyes. However, A doesn't know that everybody else sees 3 people with blue eyes, only that they see at least 2. Also, A doesn't know that B, C, and D know that everybody else sees at least 2 people with blue eyes, only that they know everybody else sees at least 1 person with blue eyes. Finally, A doesn't know that B, C, and D know that everybody else knows that everybody else sees at least 1 person with blue eyes, meaning A believes it possible that B, C, and D believe it possible that somebody believes it possible that somebody doesn't see anyone with blue eyes.

This changes with the oracle's announcement. As soon as nobody leaves on the first night, A does know that B, C, and D all know that everybody else knows that everybody else sees at least 1 person with blue eyes.

With each successive night, that number increases by one. Thanks to the Oracle's public announcement, on each night the chain will stop when you reach $n$ people with blue eyes.

If you focus on what people do, you'll see there is no magical difference between $k=3$ and $k=4$, or $k=4$ and $k=5$

Here's another way to consider the situation - if you are trying to distinguish between two possibilities (whether or not you have blue eyes), you can use the behavior of other people (when other people leave or not) to help you determine which possibility is true.

The first few scenarios for low numbers of blue-eyed people are easy to decide. If there's only one, they'll leave on the first night. If there's only two, then when the other doesn't leave on the first night they know their eye color and both will leave on the second night.

With that as a basis, now consider the scenario where you see $n$ blue-eyed people. You have no way to initially determine if there are $n$ blue-eyed people and you have a different eye color, or if there are $n+1$ blue-eyed people with you being one of them.

However once the oracle makes the announcement, you do have a way to determine the difference - whether or not the blue-eyed people you see leave on the $n$th night.

If you think people would leave when $k=3$ but not when $k=4$, how would that happen? When $k=3$, they will leave on the third night. If $k=4$, they will not leave on the third night. Then in the morning, everyone with blue eyes will know there are 4 people with blue eyes, and they must be the fourth person.

The same logic holds for the next step. If people would leave when $k=4$ but not $k=5$, how does that happen? For $k=4$ people will leave on the fourth night, but when that doesn't happen the five blue-eyed people will know that there must be five people with blue eyes.

Answer 3

Regardless of whether the guru creates new knowledge about what people know about eye color, can we all at least agree that the Guru's statement is necessary in order to start the clock, because the Guru is the only one that can communicate (in this phrasing of the problem)?

The islanders are not allowed to communicate in any way, so there is by definition no way for them to synchronize absent the Guru.

One might guess that they all know when they arrived on the island (i.e. that there is a "day 1"), but that would be only a guess... it's not stated in the problem that the islanders know when everyone arrived, or how many days have passed since that happened, nor that they haven't arrived sequentially, nor anything else about their arrival or when "day 1" might have been. Indeed, it is stated that their years on the island are "endless".

And, critically, without communication there is no way to know that everyone knows at least that, since it's not part of their defined starting knowledge that they know everyone knows.