Blue eyes and red eyes (The blue-eyed islanders puzzle)

Blue eyes and red eyes (The blue-eyed islanders puzzle)

Australian Chinese mathematics prodigy Tao Zhexuan once posted a question on the Internet,  The blue-eyed islanders puzzle, to  make everyone think and play.

Say that there are 100 people on an island, of which 5 have red eyes and 95 have blue eyes. There are three strange religious rules on this island.

1. They cannot look in the mirror or see the color of their eyes.
2. They can't tell others the color of each other's eyes.
3. Once someone knows the color of his eyes, he must commit suicide at noon the next day.

Note: Although the title has 5 red eyes, the islanders do not know the specific number. (Because they can see each other, all the blue-eyed people on the island know that there are red eyes on the island)

One day, a traveler came to this island. Because he didn't know the rules here, he inadvertently said a word when he was partying with all the people on the island: "You have people with red eyes here."

The final question is: Assuming that the people on this island are smart enough, everyone can make careful logical reasoning. What will happen on this island?

As a result, five people committed suicide on the island after the fifth day, all of whom had red eyes. Why?

proving process:

Mathematical induction

The first answer to this question is derived by mathematical induction: if there are N red eyes on this island, then on the Nth day when travelers say this, all of them will commit suicide. Specifically for this question, on the 5th day, all 5 red eyes on this island will commit suicide. (Respect the original question, supplement: After the red eyes committed suicide collectively, the other blue eyes knew their own eye color and also committed suicide).

If there is only one red eye on this island, everyone else has blue eyes. Then, when the traveler said this, the person immediately knew that he had red eyes, because the others he saw were blue eyes, and he would commit suicide on the same day. That is, when n takes the first value n0 = 1, the proposition holds.

Suppose that when there are N red eyes on this island, on the Nth day after the traveler said this sentence, all these red eyes will commit suicide.

Then, when there are N + 1 red eyes on this island, in the eyes of each red eye, there are definitely N red eyes on the island, and they wait for them to commit suicide on the Nth day. On the Nth day, no one committed suicide. So on the N+1th day, every red eye understands that there is still the N+1th red eye on this island-himself. So everyone committed suicide on the N+1 day.

So the proposition is proved: if there are N red eyes on this island, then on the Nth day when travelers say this, all of them will commit suicide.

Exhaustive reasoning

If the above proof is still confusing, you can also use the exhaustive method to prove it.

When there is only one red eye on the island, the day the traveler finishes saying this, he will commit suicide. This is no doubt.

When there are two red eyes on the island. On the day the traveler finished saying this, the two red eyes were waiting for the other to commit suicide, but the other did not commit suicide. So on the second day they immediately realized that they were also red eyes, so they committed suicide the next day.

Reasoning down from this, when there are three red eyes on the island. After the traveler said this sentence, each red eye was waiting for the other two red eyes to commit suicide collectively the next day, but they did not commit suicide. So on the third day, everyone understood that they had red eyes, and they committed suicide together.

And so on. This leads to the proposition: If there are N red eyes on the island, then on the Nth day after the traveler finishes saying this sentence, the N red eyes will commit suicide together. Specifically for this question, on the fifth day, the five red eyes committed suicide together.

Is it a paradox?

But, actually think about it, the traveler said, "There are people with red eyes on this island?" The fact that people on the island already know, so this question seems to be a paradox.

Common knowledge and common knowledge

In fact, this question is not a paradox.

First of all, people on the island, some people know in their hearts that there are people with red eyes on the island (people with blue eyes can see people with red eyes, and people with red eyes can see other people with red eyes (if the number of people with red eyes) Greater than 1)), however, everyone does not know whether others already know that there are red eyes on this island. Travellers also let everyone know that there are people with red eyes on the island, and everyone else knows this fact. For example, when there is only one person with red eyes, all people with blue eyes know that they have red eyes, but people with red eyes don't.

• Shared knowledge: The knowledge that everyone knows is called shared knowledge.
• Public knowledge: 1. Knowledge is shared knowledge, 2. Everyone knows that other people also know this knowledge.