Saturday, January 11, 2014

1000 creative islanders

The thousand islanders problem is a reasonably well known problem which goes like this.

On a certain island there live 1000 people, who follow a strange religion (possibly not as strange as some real world ones but still pretty strange). The two tenants of this religion are that everyone must attend the daily gathering  at noon in the village square and that should an adherent learn their own eye colour they must commit suicide at the next daily gathering in front of the whole village.

The result of this is of course that these islanders have no mirrors and that no one ever mentions anyone else's eye colour. As a further departure from reality in the world of the islanders everyone has either blue eyes or brown eyes (so for example no green eyes, yes it's an oversimplified world so that the puzzle works just go with it).

It's also common knowledge that everyone has one of these two eye colours. By common knowledge I mean everyone knows this, and everyone knows that everyone else knows, and everyone knows that everyone else knows that everyone else knows etc etc. As it happens exactly 100 of the 1000 islanders has blue eyes (for the innumerate readers who're probably on the wrong blog, this means the other 900 have brown eyes).

One day a stranger arrives on the island and being ignorant while being feasted (in the evening after the daily gathering but still in front of the whole island) makes the following remark "How interesting to see another blue eyed person in this part of the world".

The usual question is then  "Does anyone actually need to kill themself?" If you don't know the answer you might want to go think about things before reading any further.

Assuming the islanders are all perfectly logical and all know each other to be perfectly logical (and all know each other to know each other to be perfectly logical etc)  is that yeah they do need to kill themselves, those with blue eyes on day 100 and those with brown eyes on day 101.

I'll leave the reason why for the discussion (or google if you want, this post is going to be too long if I fill in details too carefully and I'm lazy). But here is an interesting extension: Suppose that some people secretly know that they are blue eyed (and have so far defied the order to commit suicide). If they commit suicide early can they save the rest of the village? What if these early suicides are from true believers who don't know there eye colour (i.e. some of them are brown)?  On a less nice variation can a single  villager with a machine gun save the village by shooting a few blue eyed people at the next gathering? What if a single person gores out there own eyes?? Or just loudly shouts at the stranger "I didn't hear that but you should try this particular desert."

No comments:

Post a Comment