Blue-eyed islanders: a solution

Follow up to Product & Sum.

As in the “three wise men” puzzle, it’s useful to begin by analyzing simplified variants of the problem. Lets start analyzing the variant where only one islander has blue eyes and the other 999 have brown eyes.

When the foreigner gives his message, as the blue-eyed islander can see that the other islanders are all brown-eyed, he now knows his own eye color and must commit suicide the following day at noon. But, when the blue-eyed islander kills himself, all the other islanders know that they are brown-eyed and they must commit suicide at noon the next day (we can assume that each islander knows that his eye color is either blue or brown).

Now we can examine the variant where two of the 1000 islanders are blue-eyed. In this case the foreigner’s message does not give any information immediately, as any inhabitant of the island knows by observation that there is at least one blue-eyed islander. But the absence of a suicide at noon the following day shows to each of the two blue-eyed islanders that the other one is not the only blue-eyed inhabitant of the island. Then, in the second noon after the message, the blue-eyed islanders commit suicide, followed by the rest of the tribe the next day.

This reasoning can be extended to the full case, where the 100 blue-eyed islanders will commit suicide at the 100th noon since the foreigner’s message and the 900 brown-eyed ones will do the same at the following noon (the 101st).

Advertisements

2 thoughts on “Blue-eyed islanders: a solution

  1. Demian says:

    While I enjoyed your solution to the Product &Sum problem, I think this one is not so satisfying.

    First of all, I don’t think the brown-eyed islanders can deduce their eye color, as there is no indication in the story you posted before that they know only blue or brown-eyed people exist.

    Then, It would have been cool if you showed why the following argument is incorrect:

    “Nothing happens after the visitor’s message, as everyone already knows that there are many blue-eyed people in the island, and everyone knows that everyone knows that. The message does not introduce any new information.”

    This argument as well as the inductive one, where the 100 blue-eyed islanders commit suicide at the 100-th day after the visitor’s address, seem pretty logical. But they yield different results. So at least one must be wrong.

    Understanding why the argument I quoted is wrong (i.e: how does the visitor’s message introduce new information) took me quite some time. But it is quite fun and requires some wicked logic.

    It can be done inductively as well. First, if there where only n = 1 blue eyed people, it’s evident that the visitor’s message introduces new information, at least for that one unfortunate islander. But it introduces new information for the other islanders as well: now they know the blue-eyed also knows there is at least one blue-eyed islander, so if he does not commit suicide that noon then there must be two blue-eyed islanders (luckily, he is devoid).

    Then, for n = 2, it’s easier for me to analyze it from one blue-eyed islander point of view. “I” already know there’s at least one blue-eyed islander. But I don’t know if he knows that. Once the message arrives, I know he knows that. And that is also true for him. That is the now information the message introduces in this case. The reasoning after that remains the same: if he does not commit suicide this noon, then I am blue-eyed as well, and we both suicide tomorrow noon).

    For n > 2 it’s quite more difficult to see it, as one have to think in terms of “I don’t know if blue-eyed islander 1 knows that blue-eyed islander 2 knows that … blue eyed islander n – 1 knows that there are blue-eyed islanders”. And once the message arrives, one knows that, and knows every one else knows it too.

    Well… It’s a difficult problem to explain for me, so I don’t expect to have been completely clear =P. My limited human-brain can only think up to n = 3 or 4 before needing to rely on a generalization to “see” it.

    Well. I just wanted to comment that. Bye!

    • mchouza says:

      First of all, I don’t think the brown-eyed islanders can deduce their eye color, as there is no indication in the story you posted before that they know only blue or brown-eyed people exist.

      Well, they know that these are the eye colors of all the people they have seen, so it’s not totally unreasonable. But it’s true that it’s not specified in the original problem, that’s the reason of the clarification “(we can assume that each islander knows that his eye color is either blue or brown)”. Maybe it would have been better to explicitly say that the last mass suicide is conditional to the islanders knowing this fact.

      Understanding why the argument I quoted is wrong (i.e: how does the visitor’s message introduce new information) took me quite some time. But it is quite fun and requires some wicked logic.

      Yes, it’ s essentially the concept of common knowledge. I was thinking of editing this post to add an explanation, but it’s better to give an entire post to the concept of common knowledge, as it entirely deserves one.

      Well… It’s a difficult problem to explain for me, so I don’t expect to have been completely clear =P. My limited human-brain can only think up to n = 3 or 4 before needing to rely on a generalization to “see” it.

      It’s mathematics. 😀

      But I will try to get a bit more used to the concept of common knowledge writing another post about this problem (this one was a bit rushed…).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s