Recursive function to reverse a String
August 7, 2012
Print the first repeating character in String
August 7, 2012

Blue Eyed Islanders puzzle

1000 tribal people lives on an island. Out of them 100 have blue eyes and 900 has black colored eyes.
Their religion forbids them to know their own eye color, or even to discuss the topic (there is no reflective surface where they can see their eyes). But all of them knows the eye color of everyone else (rest 999).
The Ritual is that if some comes to know his own eye color (directly or thru inference) he/she will commit suicide in the afternoon (for all to witness).
One day a blue-eyed traveler came to the island and while leaving he announced (to all) “I am glad to see another blue-eyed person like me“.
The question is, What will happen after the announcement?
Please assume that all the tribal people are logically sound (If a logic can be deduced they will derive it instantly).
Solution:

There are two very strong convincing arguments to the solution to this problem:

1. Travelers comment will have NO EFFECT

Actually the traveler has not said anything which no one knows. Everyone on the island knows that there are blue-eyed people (Those who has blue-eyes, think there are 99 blue-eyed people and black-eyed people think there are 100 blue-eyed people). Since no one can talk to anyone else on the number of people with blue eyes, hence nothing will happen.

2. Travelers comment will have dramatic effect and all the 100 blue-eyed people will commit suicide on the 100th day

The general solution is that:

“If there are n blue-eyed people (n=positive integer) then all of them will committ suicide on the n‘th day.”

If n=1.

The person with blue-eyes will realize that he is the one (because there is no one else with blue-eyes) and hence will commit suicide the same day.

if n=2.

Both the blue-eyed people will think that there is only one person with blue eyes (the other one) and hence, none will commit suicide on the same day. But on the second day, they will find that the other blue-eyed person is alive and hence will deduce that he is not the only one with blue eyes (else he would have committed suicide).

Hence on the 2’nd day both of them will die.

For any arbitrary n.

Each of the blue-eyed man believes that there are n-1 blue-eyed man on the island. Hence, he will assume that all of them will commit suicide on (n-1)’th day. But when none of them will die on the (n-1)’th day, they will infer that they themselves are also blue-eyed. Hence, all of them will commit suicide on the n’th day.

Can be proved using Principle Of Mathematical Induction

Hence, All the 100 blue-eyed islanders will commit suicide on the 100'th day.

Variation:

  1. If the traveler realizes his mistake after some days (say 10 days). Is there a way to reduce the number of people dying because of his statement ?
  2. What will happen if, on the first day and  each day after that, every islander must announce their best guess of how long they think they will stay on the island ?

1 Comment

  1. […] Blue Eyed Islanders puzzle […]

Leave a Reply

Your email address will not be published. Required fields are marked *