Text below copied from here
The Blue-Eyed Islander problem is one of my favorites. You can read
about it here on Terry Tao's website, along with some discussion.
I'll copy the problem here as well.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; 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.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?
The possible options are
Argument 1. The foreigner has no effect, because his comments do not tell the tribe anything that they do not already know (everyone in the tribe can already see that there are several blue-eyed people in their tribe).
Argument 2. 100 days after the address, all the blue eyed people commit suicide. This is proven as a special case of
Proposition. Suppose that the tribe had $n$ blue-eyed people for some positive integer $n$. Then $n$ days after the traveller’s address, all $n$ blue-eyed people commit suicide.
Proof: We induct on $n$. When $n=1$, the single blue-eyed person realizes that the traveler is referring to him or her, and thus commits suicide on the next day. Now suppose inductively that $n$ is larger than $1$. Each blue-eyed person will reason as follows: “If I am not blue-eyed, then there will only be $n-1$ blue-eyed people on this island, and so they will all commit suicide $n-1$ days after the traveler’s address”. But when $n-1$ days pass, none of the blue-eyed people do so (because at that stage they have no evidence that they themselves are blue-eyed). After nobody commits suicide on the $(n-1)^{st}$ day, each of the blue eyed people then realizes that they themselves must have blue eyes, and will then commit suicide on the $n^{th}$ day.
It seems like no-one has found a suitable answer to this puzzle, which seems to be, "which argument is valid?"
My question is…
Is there no solution to this puzzle?
Best Answer
Argument 1 is clearly wrong.
Consider the island with only two blue-eyed people. The foreigner arrives and announces "how unusual it is to see another blue-eyed person like myself in this region of the world." The induction argument is now simple, and proceeds for only two steps; on the second day both islanders commit suicide. (I leave this as a crucial exercise for the reader.)
Now, what did the foreigner tell the islanders that they did not already know? Say that the blue-eyed islanders are $A$ and $B$. Each already knows that there are blue-eyed islanders, so this is not what they have learned from the foreigner. Each knows that there are blue-eyed islanders, but neither one knows that the other knows this. But when $A$ hears the foreigner announce the existence of blue-eyed islanders, he gains new knowledge: he now knows that $B$ knows that there are blue-eyed islanders. This is new; $A$ did not know this before the announcement. The information learned by $B$ is the same, but mutatis mutandis.
Analogously, in the case that there are three blue-eyed islanders, none learns from the foreigner that there are blue-eyed islanders; all three already knew this. And none learns from the foreigner that other islanders knew there were blue-eyed islanders; all three knew this as well. But each of the three does learn something new, namely that all the islanders now know that (all the islanders know that there are blue-eyed islanders). They did not know this before, and this new information makes the difference.
Apply this process 100 times and you will understand what new knowledge was gained by the hundred blue-eyed islanders in the puzzle.