In a village, there lives 100 people. Among them, there are 95 people with blue eye, and 5 of them are with red eye. Everyone can see the eye color of the rest 99 people, but they don’t know their own eye color and they are not allowed to ask people about it or check it themselves in a mirror.
There is a strange ancient law that anyone who knows their own eye color must suicide the next day in the central park of the village. As a result, no one in the village likes to discuss about the eye color in their daily conversations.
One day, a tourist visited the village. Due to their hospitality, they held a celebration dinner for the visitor. During the dinner, the visitor gave a toast that he really enjoyed the trip and he is glad to find out that there are people with the same eye color as him- red. He didn’t mention who is red eye, but suddenly people are all in silence. The visitor realized that he has toughed on something he should not have brought up, so he left shortly after with guilt.
Question: If all the 100 people living in the village are rational people and sufficiently intelligent, what will happen?
Answer: 5 days later, all the 5 people with red eyes suicided in the central park.
The original question is from Terry Tao’s blog[1]. This question can be solved using exhaustive sampling or mathematical induction.
Exhaustive method
- At day 0, the visitor announced that there are people with red eye in the village.
- If there is only one red eye
- The one with red eye will suicide on day 1 because he sees no other person with red eye, so the red eye person must be himself
- If there are 2 people with red eye
- The 2 red eye people know that there is at least 1 red eye (could be 2 if himself is red eye, but he is not sure) and the rest 98 know that there are at least 2 red eye people (could be 3 if himself is red eye, but he is not sure)
- If there is only one red eye, then that people will suicide on day 1
- If day 1 there is no one suicide, then he knows that there is one more red eye and that must be him, so he will suicide on day 2; the other people with red eye will think the same way so they will both suicide on day 2
- If there are 3 people with red eye
- The 3 red eyes know that there are at least 2 red eyes (could be 3, but he is not sure); the rest 97 know that there are at least 3 red eyes (could be 4, but he is not sure)
- On day 1-2, nothing will happen
- On day 3, since no one died on day 2, the 3 red eyes now know that there are more than 2 red eyes, and himself must be with red eye, so all the 3 red eyes will suicide on day 3
- Following the same logic, if there are N people with red eye
- No one will die during day 1 to (N-1)
- On day N, all the N people with red eyes will suicide simultaneously
Mathematical induction:
- If there is only one people with red eye, he will realize himself immediately that he is the one with red eye, so he will suicide on day 1. So, the hypothesis is valid when N=1.
- Now assuming: if there are N people with red eye, they will all suicide together on day N after the visitor’s announcement.
- On day N+1, from the perspective of the people with red eyes, they all know with certainty that there are N people with red eyes in the village. They are waiting for all the N people to suicide on day N. However, no one died on day N, so now they know that there is one more person with red eye, and that’s himself. So, all the N+1 people will suicide together on day N+1. The hypothesis is thus true for case n=N+1.
- Therefore, by mathematical induction, the statement is true: if there are N people with red eye, then all N people will suicide on day N.
So here seems to be have a paradox: what new information did the visitor bring by announcing that there are people with red eye in the village? Isn’t that something people already know?
Yes, there are new information. Before the visitor makes the announcement, ‘there are people with red eye’ is a mutual knowledge. However, after the announcement, it becomes ‘common knowledge’.
[1] https://terrytao.wordpress.com/2008/02/05/the-blue-eyed-islanders-puzzle/
