The Blue Eyed Islanders

General Chat
1

This thread is about one of my favorite logic puzzles, The Blue Eyed Islanders. It has been retold by many people, with different variations and wordings, but it’s not a puzzle about language, and instead just about logic.

Here is an exemplary presentation by xkcd: Blue Eyes - A Logic Puzzle

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?

xkcd’s discussion of the solution (spolier): Blue Eyes - The Hardest Logic Puzzle in the World - Solution

The Fields medalist Terence Tao has a few blog posts about it

Relevant Wikipedia article

:eyes:

5 Likes
2

Yes, I love epistemic puzzles!

Here’s one variant that I like, since it’s the puzzle in reverse in a way. Let N be some positive integer.

Suppose that on the island there lives exactly one person with blue eyes, and one person with brown eyes. What should the Guru announce to them to make sure that these two people leave after exactly N days?

3 Likes
3

Why does it take the observation of the Guru to trigger off the exodus?

Why don’t they all leave as soon as they start thinking about this (n days after).

I can’t see what changes before and after the Guru speaks: they already know what they are told by the Guru, so they all should have left already.

4

Although everyone knows there are people on the island with blue eyes, it is not common knowledge that there are people with blue eyes, and that’s an important difference.

Probably it’s easiest to understand by starting small. Suppose there is only 1 person on the island, who has blue eyes: Obviously when the Guru says that there is someone with blue eyes, this one person will leave the next day, since there’s nobody else to see with blue eyes.

Now imagine there are 2 people with blue eyes, Anna and Bob. Although both of them know that there are people with blue eyes on the island already (they both can see one), they don’t know that everybody knows there’s people with blue eyes. For example, Anna could imagine that she has blue eyes, but also that she has brown eyes. In the latter case, Bob would not be able to see anybody with blue eyes, and thus leave on the next day. The fact that Bob does not leave, means that Bob was not the only one with blue eyes, and thus Anna could conclude from that that they both must have blue eyes.

Now, let’s go to 3 people with blue eyes, Anna, Bob, Claire. It’s again the case that everybody knows that there is someone with blue eyes. This time, it’s also the case that everybody knows that everybody knows that there is someone with blue eyes: everybody sees two people with blue eyes who therefore can see each other. However, it’s not the case that everybody knows that everybody knows that everybody knows that there is someone with blue eyes. For example, Anna could not distinguish the situation from having brown eyes herself.
If Anna would have brown eyes, then Bob and Claire would only see one other person with blue eyes, and remember that that means that Bob wouldn’t know whether everybody knows there’s someone with blue eyes: in this case Bob has to account for the case where he has brown eyes, and where Claire would not be able to see any blue eyes.
So, in the hypothetical case where Anna has brown eyes, hypothetical Bob wouldn’t know that everybody knows that there’s someone with blue eyes. Therefore Anna doesn’t know whether Bob knows that everybody knows that there’s someone with blue eyes. Hence it’s not the case that everybody knows that everybody knows that everybody knows that there’s someone with blue eyes.

When we scale up, the only thing that changes, is that a person with blue eyes has to account for the case where they have brown eyes and think about what one of the people with blue eyes would see: this hypothetical person with blue eyes then would need to account for the hypothetical hypothetical case where they have brown eyes and needs to consider what one of the people with blue eyes would see: this hypothetical hypothetical person with blue eyes needs to account for the hypothetical hypothetical hypothetical case that … Etc.

Common knowledge is the kind of knowledge that could be described as “everybody knows it, and everybody knows that everybody knows it, and everybody knows that everybody knows that everybody knows it, and everybody knows that everybody knows that everybody knows that everybody knows it, and …” ad infinitum. At the time before the Guru speaks there is no common knowledge yet, but as soon as the Guru says it, this common knowledge is there, which changes the information the people have.

4 Likes
5

Thanks for that explanation.

It was very good. I could understand it as I read it.

I don’t yet understand it well enough to reproduce it, but it is a good start, thanks again.

I understood what common knowledge is (your statement of how it could be described) but I couldn’t see a scenario where it wasn’t common knowledge without someone saying it (and indeed, I still don’t understand the explanation well enough to refute the problem of “wait a minute, if I can see 99 people with blue eyes, how can it be that there is anyone who can’t see someone else with blue eyes, and why isn’t that sufficient to make us all leave?” I -juuust- have to be able to reconstruct how there can be some doubt about whether there is the possibility of a person who doesn’t know that there are blue eyes on the island)

6

You’re a fast reader, then :stuck_out_tongue:

It’s not the most intuitive thing, common knowledge.

Because it’s not enough for everybody to know there’s someone with blue eyes. It’s also not enough for everybody to know that everybody knows that there’s someone with blue eyes. We need that everybody knows that … (99 times) … everybody knows that there is someone with blue eyes.

Why do we need it 99 times? Well, since if there were only 99 people with blue eyes, then any of these 99 people would only see 98 people with blue eyes, and therefore needs to know that everybody knows that …(98 times) … everybody knows that there someone with blue eyes. For them, there’s the hypothetical case that there’s only 98 people with blue eyes, and any of these hypothetical people would only know that everybody knows that … (97 times) … etc.

Thus, by going 99 hypothetical layers deep, without the announcement there would be a lack of knowledge, since this 99th hypothetical case would only have 1 person with blue eyes, who wouldn’t see anybody with blue eyes and thus wouldn’t know that there’s people with blue eyes yet.

So, with 100 people, everybody knows that there’s someone with blue eyes, and everybody knows that everybody knows this, and everybody knows that everybody knows that everybody knows this, and everybody knows that … (N times) … everybody knows this (for any N below 99), but it’s not the case that everybody knows that …(99 times) … everybody knows that there someone with blue eyes.

I think it’s best to carefully study the difference between the case where there’s 2 people and the case where there’s 3 people. That’s probably the most enlightening, at least a lot more than the case with 99.

5 Likes
7

Hah. Can you run it again: why is it important that everybody knows that everybody knows that… N times?

Where in the induction do we depend on the N times of everybody knowing?

In your description, you unwind from the end - from the 99th case, but I can’t see why the original statement of induction depends on it.

(Meanwhile, it’s actually hard to hang on to the meaning of N-2 of the everybody knows’s! The first two are easy, but the third and beyond are elusive like reading a more than 2 moves ahead on the go board!)

2 Likes
8

Ok, but let’s introduce some notation. I’ll write P for “there is someone with blue eyes” and E( … ) for everybody knows that ( … ).

If there’s 1 person with blue eyes, then it’s not the case that E(P), since this 1 person doesn’t know P. Hence, the effect of the announcement is that the 1 person suddenly learns that P.

Suppose that there’s 2 people with blue eyes, then it’s the case that E(P), but not the case that E(E(P)). For either of the people, they can’t distinguish their situation from the situation where there’s only 1 person with blue eyes. This hypothetical case is the previous induction step, and we just learnt that not everybody there knows P.

Suppose that there’s 3 people with blue eyes, then it’s the case that E(P), and also that E(E(P)), since everybody can see 2 people with blue eyes, who can see each other. It’s however not the case that E(E(E(P))), since any of the people with blue eyes cannot distinguish the actual situation from the hypothetical case that there are only 2 people with blue eyes (the previous induction step).

Hence, in the situation with N people with blue, it’s not the case that E(…E(P)…), with N many E’s. For any of the people with blue eyes, there’s the hypothetical case where there’s N-1 people with blue eyes. In such a world, it would not be the case that E(…E(P)…) with N-1 many E’s.

Now assume that we know that if there are N people with blue eyes, then they will leave after N days, and we want to prove that if there are N+1 people, they leave after N+1 days. For any of the N+1 people with blue eyes, the situation is indistinguishable from the situation where there’s only N people with blue eyes. Therefore, if there’s only N people with blue eyes, by induction they would leave after N days. But they don’t (since there’s N+1 people with blue eyes). Therefore, after N days, everybody learns that there must be N+1 people with blue eyes and leaves promptly.

2 Likes
9

(I think your first sentence means “it’s not the case that E(P)”)

2 Likes
10

(I started with P meaning “everybody knows there someone with blue eyes” and then half-heartedly changed only some of the expressions afterwards)

2 Likes
11

This forum went from
GO → Memes → werewolf → languages → pedants → and now probability

4 Likes
12

This isn’t probability, it’s pure logic / philosophy. Epistemology to be exact.

3 Likes
13

I got acquainted with this puzzle from a more beer-friendly version:

A village has 100 couples, and the village rule stated that any husband who found out that his wife has comited adultery must kill his wife and then commit suicide at sunrise after he found out. Each husband knows that all 99 wives of the other men had commited adultery (the reason why he knows cough), but believe his own wife innocent because the other men don’t share that info with him, not wanting him to commit suicide.

One day a traveler passed by and stayed for a while, and the night before he left, on the bar he slipped a comment on the truth that one of the women in the village gave him a night he wouldn’t forget.

2 Likes
14

I believe there are several problems with this formulation of the puzzle.

1.) In the eye-color formulation, not only does everybody know the eye-color of all other people, but it is common knowledge that everybody sees the eye color of everybody else. This does not seem to be the case here, and I believe this is a crucial part of the solution.

In words, whenever an inhabitant considers the perspective of another person on their wife, there are not only two cases to consider (as was in the eye-color version, where they either see Blue or non-Blue), but now there are 3 possible cases, namely 1.) they know my wife comitted adultery 2.) they know my wife did not commit adultery 3.) they don’t know whether my wife committed adultery or not.

2.) The traveler appearing introduces the possibility that a wife who previously had not committed adultery changes this, i.e. Whenever we consider an inhabitant that knows that my wife did not commit adultery, they would have to question whether or not this fact is still true. Compare it to the eye-color version, where this kind of change in nature is not possible.

2 Likes
15

I believe Martin is right here.

If the village has 2 couples, then after the statement of the traveller, both husbands could believe that their wife is faithful and that the wife of the other husband must have committed adultery.

If the statement were to be that the traveller witnessed one of the wives committing adultery with one of the husbands, the problem may still not be solvable.

Here, both husbands may believe that the traveller witnessed them comitting adultery with the other wive, and still have no evidence that their own wife was cheating.
Although, on second thought, that in itself means that them staying alive the next day must mean they both have committed adultery. By process of elimination this means on the second day both husbands know the other committed adultery and thus has evidence that their own wife must have done so as well.

Let’s scale up to three husbands Adrian, Bob and Charles, with wives Alice, Barbara and Cecile. Let’s say Adrian cheats with Barbara, Bob with Cecile and Charles with Alice.

After the initial announcement, none of the husbands has reason to believe their own wife has been unfaithful. There is furthermore no process of elimination after the second day: Adrian for example may believe that both Bob and Charles cheated with Cecile or Barbara respectively, and thus that Alice must be faithful.

So perhaps we can solve this by stating that cheating husbands & wives spend the entire night together?

Still not! Since that would mean the three husbands not committing homo-/suicide on the first day implies all three were cheating, thus all wives must’ve been cheating as well.

2 Likes
16

Yeah, I think the adultery version is more of a joke (assuming familiarity with the standard eye-color version). There are a lot of assumptions that are natural with eye color: you can see my eye color, I know you can see my eye color, other people know I know you can see my eye color, and so on.

With adultery, not only does each man have to know whether every other man’s wife has committed adultery, it also has to be known that each man knows this, and so on…

Also, the statement of “believe his own wife innocent” is a bit tricky, since one needs to be careful about understanding how strong that “belief” is, and whether it could be changed by evidence. With the eye color version, everyone starts out as simply uncertain about their own eye color.

2 Likes
17

I think with this epistemic puzzle, we could interpret “believe” as “knows” for the puzzle to work. If we’re working with proper belief, that is conviction of a possibly false statement, the puzzle becomes a lot more messy.

1 Like
18

A branch of the Dutch version of the FBI / CIA publishes a Christmas puzzle each year with usually some fiendishly hard cryptographic puzzles. They posted an epistemic puzzle as well a couple of years ago that was quite cute.

Three spies, A and B and C, have knowledge of the date of a special occurrence. A only knows the month of the occurrence, B only knows the day and C has figured out all possible dates for the special occurrence, and shows it to A and B:

image
image1470×1534 259 KB

A states that from this information neither of them know the date.
B then responds that this was true, but now that A said this, B knows the date.
A then immediately responds that A knows the date as well now.

What is the date of the special occurrence?

hint

As a warm up, consider figuring out Cheryl’s birthday.

2 Likes
19

It’s essentially the same puzzle as Cheryl’s birthday, except this version requires some tedious counting to figure out which are the exact dates highlighted in the figure.

20

Yes… Hence the hint.