3
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ Posting text as images is frowned upon. Can you edit the post to provide a text alternative? SEE: meta.stackexchange.com/questions/356997/… $\endgroup$ Sep 22 at 14:42
  • 1
    $\begingroup$ Theorem 0 is not correct. For example, if there are initially 100 blue-eyed people on the island, then before the oracle speaks, it is not the case that "everybody knows that everybody knows that... everybody knows that there is at least one blue-eyed person", where the phrase "everybody knows that" occurs 100 times. But after the oracle speaks, it becomes true. So the oracle does provide new information. $\endgroup$
    – fblundun
    Sep 22 at 17:23
  • $\begingroup$ @fblundun Why is "everybody knows that everybody knows" not the stopping condition? The uncertainty does not grow serially if there is no uncertainty in parallel. A>B>C>D does not matter if ABCD > ABCD because A>D, B>D, C>D, D>D so in A's hypothetical of A>B>C>D he does in fact know that C>D. $\endgroup$ Sep 22 at 17:37
  • 1
    $\begingroup$ If A knows that everybody knows that everybody knows that there is somebody with blue eyes, then A cannot deduce that B knows that C knows that D knows that somebody has blue eyes. A can only deduce that B knows that C knows that there is somebody with blue eyes. $\endgroup$
    – fblundun
    Sep 22 at 18:22
  • 1
    $\begingroup$ @AcumenSimulator I think this other question seems similar to this one (though coming to the opposite conclusion). Perhaps some of your doubts could be answered there? Specifically, "the sky is blue" is different because you're looking at the same sky as everyone else. But people aren't all looking at the same blue eyes. $\endgroup$
    – Deusovi
    Sep 23 at 4:54
12
$\begingroup$

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!
image of eight islanders, seven labelled

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?

two copies of eight islanders, the last one colored brown in one copy and blue in the other

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.

same as previous image, but now one of the islanders in the image has their own pair of copies, both times they appear

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.

lots of nested scale models

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...

enter image description here

(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.

same as before but with all-brown models crossed out

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.

one layer of nesting, with brown model of someone else smashed

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.

$\endgroup$
3
  • 1
    $\begingroup$ I realize this answer is likely redundant with some of the many other answers that have appeared to other Blue Eyes questions, including my own answer from a year ago. But I hope the pictures, and the reframing of the mental models as physical ones, can make things slightly clearer. $\endgroup$
    – Deusovi
    Sep 23 at 6:34
  • $\begingroup$ ...also, here's a relevant xkcd that didn't really fit into the answer, but seemed worth mentioning anyway. $\endgroup$
    – Deusovi
    Sep 23 at 6:42
  • 2
    $\begingroup$ This is very interesting and helpful visual proof! I will link to this one whenever I need to explain the proof =D $\endgroup$
    – justhalf
    Sep 23 at 6:50
6
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ If you have brown eyes you see 3 people with blue eyes, therefore everyone sees people with blue eyes $\endgroup$ Sep 22 at 16:57
  • $\begingroup$ @AcumenSimulator so? If you have brown eyes and see 2 people with blue eyes you still know everyone sees someone with blue eyes. How does knowing that everyone sees someone with blue eyes help you tell the difference between these two scenarios? $\endgroup$
    – Rob Watts
    Sep 22 at 17:03
  • $\begingroup$ If you see 3 people with blue eyes you can prove that everyone sees someone with blue eyes. Not only that you can prove that everyone can prove this. If everyone can prove it, why would you think that someone doesn't know there are blue eyes? $\endgroup$ Sep 22 at 17:24
  • $\begingroup$ @AcumenSimulator what are you saying would actually happen? Are you saying that nobody would leave the island at all, or that it would not be on the nth day that the n blue-eyed people leave? $\endgroup$
    – Rob Watts
    Sep 22 at 17:27
  • 1
    $\begingroup$ I think your first statement gets to the heart of my misunderstanding. I am going to look harder into why my thought (that the uncertainty being carried along as you specified is overruled by the event being directly observable to everyone) is wrong. $\endgroup$ Sep 22 at 19:50
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.