The Blue-eyed Islanders Puzzle

I came across this engrossing logical puzzle (on this blog) and really enjoyed solving it. I am reproducing the problem statement with minor modifications here:

There is an island upon which a tribe resides. The tribe consists of 1000 people, with various eye colours. Their religion forbids them to know their own eye color, or even to discuss the topic; thus, each resident can (and does) see the eye colors of all other residents, but has no way of discovering his or her own (there are no reflective surfaces). If a tribesperson does discover his or her own eye color, then their religion compels them to commit ritual suicide at noon the following day in the village square for all to witness. All the tribespeople are highly logical and devout, and they all know that each other is also highly logical and devout (and they all know that they all know that each other is highly logical and devout, and so forth).

For the purposes of this logic puzzle, “highly logical” means that any conclusion that can logically deduced from the information and observations available to an islander, will automatically be known to that islander.

Of the 1000 islanders, it turns out that 100 of them have blue eyes and 900 of them have brown eyes, although the islanders are not initially aware of these statistics (each of them can of course only see 999 of the 1000 tribespeople).

One day, a blue-eyed foreigner visits to the island and wins the complete trust of the tribe. Before leaving the island, he addresses the entire tribe to thank them for their hospitality. However, not knowing the customs, the foreigner makes the mistake of mentioning eye color in his address, remarking “how unusual it is to see another blue-eyed person like myself in this region of the world!”

What effect, if anything, does this faux pas have on the tribe?

***

Here’s what happens, you have to figure out how this happened:

After 100 days, all blue-eyed people commit suicide.

[Hat Tip: The Big Questions]

***

Answer: Please see Ramanand’s (first) comment below for the solution. I’ve also posted two additional questions in my response to his comment.

Posted in Puzzles

Tags:

22 responses to “The Blue-eyed Islanders Puzzle”

1. Great puzzle!
Though once you mentioned induction, it’s easy to explain:

every ‘blue eyed boy’ (BEB) knows the number of blue-eyes in the island that he can see, say ‘n’.

if n=0, the person who sees 999 brown eyes knows he is the only BEB (as the visitor has confirmed the presence of least 1 on the island), so he jumps off the nearest rock.

If n=1, a BEB waits for the other BEB to jump; if after a day, the other BEB doesn’t, he realises there are at least 2 of them. So suicide pact ensues on day 2.

Apply induction and for n=100, the lemmings are seen plunging into the sea 🙂

Enjoyed this!

• Vishal

You are right, I took out the reference to ‘induction’. This puzzle also introduced me the logical concept of “common knowledge“, which I found very interesting.

• So I asked this puzzle to quite a few people at work (I work in an R&D group largely made of CS people, but some non-CS as well) as well as home. Some of them were not into puzzles.

Since I had the luxury of sitting with them and taking them thru the puzzle/answer/solution. Initially, I left out the reference to Induction, and none of them got the answer. Then gave the answer. Then followed up with the induction clue. I found that reasoning with induction was slightly counter-intuitive for most non-CS people (wonder if all the CS people are comfortable with it or have just made their peace with it!)

“Common Knowledge”: thanks for the term. I had some trouble articulating the concept to some people because the idea of people making the same inferences just based on thinking and without any communication/hints/winks was hard to grasp for some.

All in all, very enjoyable to solve as well as to learn from how people think!

2. Vishal

Ramanand,

There are two more very interesting questions (especially the second one below) that can keep your left brain occupied for quite some time:

(1) If someone can not solve the puzzle, ask her the following question: What if the traveller had said “how unusual it is to see another green-eyed person like myself in this region of the world!” (In short, he lied!)

[As you can see, this one is easy to solve. And once someone solves it, that logical chain of thought might help solve the main puzzle as well.]

(2) Going back to the original puzzle, the big (and quite fascinating!) question is: what additional piece of information is conveyed through traveler’s remark?

The traveler’s message can be interpreted as “at least one of you guys have blue eyes.” Now, didn’t the villagers already know that? How is this information new?

• Vishal

Oh, I forgot to ask, what do you mean my “CS people”? Computer Science?

3. yes, CS – computer science (I learned induction only via my discrete maths syllabus while studying it). Most of my non-CS friends haven’t studied induction.

interesting qns – will think of them! For the case of 999-1, the foreigner’s information is new to the only blue-eyed boy (trivial). But this info causes this change in common info is fascinating – will think about it.

• Vishal

I have a CS degree myself! May be that’s what helped me to solve/understand this puzzle:

Here’s the answer to the second question in my last comment above:

For simplicity, imagine that there are only four blue-eyed persons on the island: A, B, C and D.

Here is a list of some of the things that ‘A’ knows:

1. (A knows that) there are at least three blue-eyed persons: B, C and D.

[He himself might be the fourth one, but he doesn’t know that. He could very well be a brown-eyed person.]

2. (A knows that) B knows that there are at least two blue-eyed persons: C and D.

[Now in reality, B knows that there are at least three blue-eyed persons: A, C and D. But A has no way of knowing that. From A’s point of view, B can see C and D.]

3. (A knows that) B knows that C knows that there is at least one blue-eyed person: D.

[Same logic as above. In reality, C knows that there are three blue-eyed persons: A, B and D. But from A’s point of view of B’s point of view, C can only see D.]

4. (A knows that) B knows that C knows that D knows that there is no one with blue-eyes.

Now when the traveler remarks that there is at least one blue-eyed person on the island, an additional piece of information gets added to the things that A knew. Because of his remark, # 4 now becomes:

(A knows that) B knows that C knows that D knows that there is at least one blue-eyed person.

That’s the additional piece of information that’s conveyed by traveler’s remark!

Note that this additional piece of information is conveyed instantly when the traveler remarked that there’s at least one blue-eyed person. The only reason all blue-eyed people had to wait for 100 days before committing suicide is the following:

In our example, A found out that B knew that C knew that D knew that there was at least one blue-eyed person. But A didn’t know that it’s him. He would have to wait for 4 days before realizing that.

P. S. Drawing a chart might help to get a clear understanding of the ‘additional piece of information’.

• Loved the explanation.
Now, pardon my stupid question about the original puzzle: after 101 days, wouldn’t all the rest of the islanders (900) commit suicide?

• Sorry for spamming.
In my comment above, I had assumed that the islanders know that eye color can be ONLY blue or brown

• Raja,

Based on your assumption, the answer to your question is ‘yes’. On the 101st day, all islanders will have to commit suicide.

However, the puzzle posted here states that “Of the 1000 islanders, it turns out that 100 of them have blue eyes and 900 of them have brown eyes, although the islanders are not initially aware of these statistics“, so in this version, only the blue-eyed folks will have to commit suicide. Each of the remaining 900 islanders will never know if their own eye color matches with the other 899.

• They don’t have to be aware of the distribution. If they know that eye color can be either blue or brown (and nothing else), then n blue eyed people will commit suicide after n days, and the rest will commit suicide the day after. Think of it.

• Yes, if we assume that they know that the eye color can be either blue or brown, then you are right. 🙂

4. C. R. Turang

There are other versions of this old puzzle. For example, from “Littlewood’s miscellany”,

Three ladies, A, B, C in a railway carriage all have dirty faces and are all laughing. Suddenly all of them realize that they themselves have dirty faces and stop laughing.

I also do know that something like this was a question on a computer science Ph. D. qualifying exam at the graduate school I went to.

• Vishal

Yeah, that’s a good one! I am reproducing the entire puzzle here for the interested reader:

Three ladies, A, B, C in a railway carriage all have dirty faces and are all laughing. It suddenly flashes on A: why doesn’t B realize C is laughing at her? – Heavens! I must be laughable. (Formally: If I, A, am not laughable, B will be arguing: If I, B, not laughable, C has nothing to laugh at. Since B doesn’t argue, I, A, must be laughable.)

Thanks for stopping by, and for your comment.

5. The reason people will not come up with the popular answer is not because they do not understand logical reasoning, inductive or otherwise. The popular solution makes a logical error and builds huge heavenly castles upon it. If there are more than two blue-eyed islanders, and no one knows the total of them, then no will expect anything to happen on the first day or the x day. There is no new information after the first day of no one leaving/dying, and there is no logical reason for the islanders to go through the same “if there are x blue-eyed people, then they will leave/die on the x day” reasoning. As an islander, it is more logical to assume that you will not have any new information on the 2nd or the x day and will never know for sure what color eyes you have, and that you therefore should do nothing.

• Vishal

Your explanation heavily relies on the assumption that “no one knows the total of them”. That assumption changes the puzzle.

(And, in that version, as long as the islanders have an idea about approximately how many blue-eyed people exhibit the island, eventually – after a long time passes – they will realize and commit suicide.)

6. pure

SOLVED

If any blue eyed person was aware of the stats of the island, he’d commit suicide by reasoning out the missing blue eyed person is himself.
Secondly, the traveler telling everyone that he sees a blue person would have no impact, his observation would already have been observed by everyone beforehand since theres 100 people walking around with blue eyes.
So basically, unless they knew the stats of eye color population then they wouldn’t be able to determine anything past a hunch. This logic puzzle is illogical, and people solved it with bs reasoning.

• no one knows the actual stats of the island
they just know what they see
each blue eyed man(all the 100 blue eyed men) knows there are
99 blues and 900 browns and himself unknown
so after the tourist declares there is atleast one blue

FIRST thought process : if only one was blue eyed he would know as it is himself and commit suicide.

SECOND thought process: if two were blue say a and b, then one of the blue say a will believe that if he is not blue(unknown colour) then b ,who originally knew there were no blue eyed,will go through the FIRST thought process and die,but a sees that the b is not going through the first thought process so that means b also knew there was one blue eyed so it has to be him so they both suicide.

third thought process: if there were 3 blue eyed, say a,b,c. then one of them say c will believe that if he is not blue(unknown colour) then both a and b will go through the SECOND thought process and die.but a sees that the a and b are not going through the SECOND thought process so that means a and b also knew there was two blue eyed so it has to be him so all three suicide.

FOURTH thought process: if there were 4 blue eyed, say a,b,c,d. then one of them say d will believe that if he is not blue(unknown colour) then a b and c will go through the THIRD thought process and die.but a sees that the a b and c are not going through the THIRD thought process so that means a b and c also knew there was three blue eyed so it has to be him so all four suicide.

FIFTH…..

SIXTH..

HUNDREDTH ONETH thought process: as there were 100 blue eyed, say a1,a2,a3…a100. then one of the other colours say b101 will believe that if he is not blue(unknown colour) then a1,a2,…a100 will go through the HUNDREDTH thought process and die.AND THIS TIME IT HAPPENS .a1 to a100 go through the hundredth thought process and suicide. so his belief was correct…..

ufffff…. i have broken the induction for all who have failed to do so 🙂

• Excruciating, huh! But you got it!