There is an island upon which a tribe resides. The tribe consists of 1000 people, with various eye colours. Yet, their religion forbids them to know their own eye color, or even to discuss the topic; 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 person 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 people 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).
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. One evening, 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?
100 days after (100 noon's after) every blue eyed islander will commit suicide in the square. The next day (and forever) will remain 900 brown eyed people only...
ReplyDeleteI published a more general version of this riddle in my book [http://libreriarizzoli.corriere.it/Congetture-su-interrogativi-inediti-tra-speculazioni-voli-pindarici-e-riflessioni-spicciole/gV.sEWcWBzMAAAE4180Y.Sgb/pc?CatalogCategoryID=VBqsEWcWo.4AAAErocUdhq_J&Root=eBook]... it's in Italian.
great!!!! Can you tell us why all blue eyed islander will commit suicide?
ReplyDeleteMost of the people here cant read italian!!
Thank you... the original puzzle was posted on the Epimetheus Society (members only) yahoo board and I was the only one to solve it at the time (2009 or so). Here you can read my original solution (Ctrl-C, Ctrl-C) - the problem was little different:
ReplyDelete"" I started my method thinking if I’m a blue eyed man and I looks around after the Guru said there is at least a blue eyed person. I see at least 99 blue eyed people (but it’s possible I’m the 100th) and 100 brown eyed people. This is a problem for me, because if there was no other blue eyed people I would have been sure I’m the only one and I can leave the island with the next ferry. Obviously this is not possible if I have brown eyes, but I don’t want to take into account that possibility.
If there is only another blue eyed people (the number of not blue eyed people isn’t important – 10, 100, 9^9^9^9, isn’t important), I can say (because of he is a perfect logician like me) he can look at me and leave the island if he see I haven’t blue eyes (I can have red eyes, green eyes etc… it isn’t important). So, if he remains, I know I have eyes of the same color of him (blue). Unfortunately I don’t have this information until he lost the ferry next night, so I can leave the island only the second time the ferry stops (and he could do the same – you can see the previous paragraph from the other blue eyed people -). So we’ll leave the island the second night together.
If there are 3 blue eyed people I have to add a step to the previous reasoning method, because, the blue eyed people of the previous step have to do what I would have done in the previous paragraph, so I have to wait one more ferry stop (and the firsts two times the ferry will leave our island without people).
The previous process is iterative and the counter “k” goes from 0 (equal to other blue eyed people I can see if I’m the only one) to 99 (the real situation if I have blue eyes)…
….
….
….
k=99:
I (we, because I’m a generic blue eyed people like others) have to wait 99 ferry’s stop to be sure I have blue eyes, so we (all) can leave the island together at the 100th ferry’s stop after we listen the first time the Guru say “there are blue eyed people here”.
The formula I used is:
k=0-->1st ferry stop;
k=1-->2nd ferry stop;
…
k=99-->100th ferry stop, that is our case.
In conclusion, the 100 blue eyed people leave the island at the 100th ferry stop after the first Guru’s statement noon. The statement is at the bottom of the final result and if she says “there are brown eyed people here” only brown e. people (that are in number of “S”) will leave the island at the S-th ferry stop after the first statement. If she says there are no red eyed people no one could leave the island and if she says there are green eyed people here (we can imagine, for example, she talks under a divine inspiration), she is able to take the ferry at the first stop (even if I can ask myself: “Why she have to do this, when she is the Oracle of 200 people, there?”). ""
FORMAL PROOF FOR THIS SPECIFIC PROBLEM:
ReplyDeleteQuestion:
What piece of information does the letter provide that each person did not
already have?
To answer this question, we have to make a distinction between mutual knowledge and common knowledge. A statement "S" is said to be mutual knowledge among a group of people if each person in that group knows S. In the puzzle above, the statement that the foreigner (the letter) makes, "Cheers to one person here which has the blue eyes (there is - at least - un person here that has blue eyes)", is mutual knowledge, since everyone knows it is true.
A statement S is said to be common knowledge among a group of people
if all of these statements are true:
1. Everyone in the group knows S.
2. Everyone in the group knows that everyone in the group knows S.
3. Everyone in the group knows that everyone in the group knows that
everyone in the group knows S.
... ad infinitum (Goedel docet).
The fact that there is at least one person with blue eyes is not common
knowledge, because this chain of statements becomes false on the 100th statement. Thus, by making her statement the foeigner is converting
mutual knowledge into common knowledge. Each night the sucide-square remains empty, the following statements become common knowledge:
0. There is at least one person with blue eyes.
1. There are at least two people with blue eyes.
2. There are at least three people with blue eyes.
...
99. There are at least 100 people with blue eyes.
After the 99th night without public deaths, it is common knowledge that there are 100 people with blue eyes. Therefore, all 100 blue-eyed people
will commit suicide on the 100th night.
In a generalization of this puzzle, we only add the condition that it is common knowledge that everyone has either blue or brown eyes. Also, there can be any number of islanders, with any number people possessing blue or brown eyes. Then the foreigner makes any nontrivial statement about the number people with blue eyes, where a nontrivial statement is one where some number of blue-eyed people would make it true, and some other number would make it false. If these conditions, are met, the theorem (Goedel's one) states that everyone will eventually commit suicide! Here is the kicker: The statement made by the foreigner can even be a statement that everyone knows is false! For example, you might enjoy working out this exercise:
There are three islanders. Each of them
has blue eyes. Now, the foreigner/letter makes the statement:
"Everyone has brown eyes."
As you will see, the islanders still get to leave!
P.S.
The reason for which no one will commit suicide after the blue-eyed people death is that any "not-blue" eyed people don't know that there are only two eye-colours (I'm not sure that my eyes can't be violet with pink strips XD).