Skip to main content

Blue eyed islanders

Here's an interesting logic puzzle (it is quite well known, see http://en.wikipedia.org/wiki/Common_knowledge_(logic)). The version below is from Terence Tao's blog. xkcd also has a version (http://xkcd.com/blue_eyes.html).
*****

– The logic puzzle –

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).

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?

*****

There are two contradictory solutions:


– Solution 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).

– Solution 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. \Box

As the above two solutions give contradictory conclusions, at most one of them is correct.  Which one (if any) is the correct solution, and what is the precise reason that the other solution is invalid?

Comments

Popular posts from this blog

Leadership

Check out the parody of Memoirs of a Geisha by Bobby Lee. Hilarious. Here's stuff on America's best leaders . Speaking of leadership, what makes a great leader? Do you have to be the smartest on the team? Or the best coordinator? It must really depend on the organization and job, but in general all leaders have to share similar traits. For example, I saw a brilliant basketball game today, Duke vs. Wake Forest. It's clear that Duke's leader is JJ Redick. That's because he is the most effective scorer, but also I think his will to win leads the team to achieve. Of course he is putting in perhaps the most work by scoring and playing nearly the whole 40 minutes. But he is defintely not the best defender on the team. So a leader needs to certainly be very skilled, but not necessarily the best at everything. The vision and determination is what makes a leader. Not everyone is a natural born leader. Some are better than others, by talent and nature. But I think leadership...

Yes, Taiwan Can!

I saw this image somewhere, and I thought it was nice. I hope we can spread it around! I apologize for not giving full credit, but if it's yours, let me know!

Of Mice and Men

Here's an interesting story, mice sing ! Check out the sound clip at the bottom of the page. Apparently during courtship male mice sing. This was discovered when researchers let male mice sniff on female or male mice urine, and though the original intention was to see how the male brain differentiates the pheromones, they noticed a rather complex ultrasound pattern erupted when hetero (whether there are homo mice is a question) male mice smelled female pheromones. This places mice in the same league as some other complex singing beings such as birds and dolphins! This is interesting for many reasons, but one I can think of is since mice are relatively easy to manipulate genetically, and the fact that they utilize complicated vocal patterns to court mates means perhaps mice have some simple language abilities. So we may be able to understand how language and vocal abilities develop and play such a crucial role (obviously as in birds better singers get to procreate!) in animals. We a...