I recently discovered an interesting logic puzzle which I will thoroughly analyze here.
A tribe lives on a remote island. It consists out of 1000 people with various eye colors. Everybody knows the eye color of everybody else, but has no way to find out his own (no reflective surfaces, they do not talk about it etc.). If they do find out, they are compelled to commit suicide the next day in a public place.
Each person is a perfectly logical agent and everybody knows that everybody is a perfectly logical agent and everybody knows that everybody knows etc.
It turns out that out of the 1000 people, 100 have blue and 900 have brown eyes. No islander knows that, each of them only knows the eye color of 999 people.
One day, a traveler arrives on the island. He gains the complete trust of the tribe. Also, everybody knows that everybody trusts him and everybody knows that everybody knows etc.
Unaware of the islander’s sensitive relationship to eye color, he remarks: “How intriguing to see a blue-eyed person in this remote corner of the world!”
What, if anything, happens to the islanders?
If you want to solve the puzzle yourself, go ahead and read on later.
At first sight, it seems that the traveler does not provide any new information. After all, each islander already sees at least 99 blue-eyed people. So, they know that there is at least one blue-eyed person. And if the information they have stays the same, nothing should change.
It turns out that the traveler does provide additional information and that it has drastic effects.
Solution: On the nth day after the traveler’s address, all blue-eyed people commit suicide. 1
Statement: If the tribe has n blue-eyed people, then n days after the event, they (and only they) commit suicide.
Proof: Induction on n.
If there is only one blue-eyed person (n = 1), he only sees people who don’t have blue eyes. Since he knows that there must be at least one blue-eyed person, he concludes that it must be himself. Thus, he commits suicide on the first day.
Suppose that the statement is true for some n >= 1. In a tribe with n+1 blue-eyed people, a blue-eyed person sees n blue-eyed people. He knows that there must be either n or n+1 in total, depending on his own eye color. He infers “If there are n blue-eyed people, they will commit suicide on the nth day. If they don’t, I must have blue eyes myself”. He decides to wait until the nth day. Since all of the blue-eyed people do that, nobody commits suicide on the nth day. This means that on this day, they all conclude that they must have blue eyes. As a consequence, they all perish on the next day, which is the (n+1)th day after the traveler’s statement. A brown-eyed person sees (n+1) blue-eyed people and makes the same argument. But when he sees them dying on the (n+1)th day, he concludes that there were only (n+1) blue-eyed people and that he is hence not one of them. But he merely knows that he is not blue-eyed and not that he is brown-eyed, so he lives on.
The solution follows as a special case with n = 100.
To clarify how it works, consider some simpler scenarios.
n = 2
Assume that there are two blue-eyed people P1 and P2 in the tribe.
What does P1 think after the traveler’s statement? “I only see a single blue-eyed person. If I have blue eyes, then P2 also sees a single blue-eyed person, so he is in the same situation as me, doing the same reasoning. This leads to infinite recursion, so this option is not worth exploring (deadlock). If I have non-blue eyes, then P2 does not see anyone with blue eyes. But in that case, since I know that he heard what the traveler said, he must conclude that he is the one with the blue eyes and kill himself tomorrow.”
When the next day comes, P2 does not commit suicide. Reasoning by exclusion, P1 deduces that he must have blue eyes. Since the situation for P2 is symmetrical, he comes to the same conclusion. Thus, both of them kill themselves on the second day.
n = 3
Assume that the tribe has three blue-eyed people P1, P2 and P3 and that the traveler has just uttered his words. What are the islanders thinking right now? Given that the situations are symmetric, we will consider it from the perspective of P1.
What does P1 think? “I see two blue-eyed people, P2 and P3. But I don’t know whether I have blue eyes. If I have blue eyes, then P2 and P3 are in the same situation as I am, as they both see two blue-eyed people (deadlock). If I don’t have blue eyes, then both P2 and P3 will be in the same situation. So it suffices to ask: what does P2 think?”
If P1 assumes that he is not blue-eyed, what does P1 think that P2 thinks? “I see one person with blue eyes (P3) and one without (P1). If I assume to have blue eyes, I cannot reason further (deadlock). If I assume to have non-blue eyes, then what will P3 think?”
What does P1 think that P2 thinks that P3 thinks, given that P1 assumes that he has non-blue eyes and given that he assumes that P2 assumes that P2 has non-blue eyes? “[This is P3:] I only see non-blue eyed people. Therefore, I must have blue eyes. I will commit suicide tomorrow.”
The next day arrives and P3 does not commit suicide. What does P1 think that P2 thinks, if P1 assumes that he has non-blue eyes? “[This is P2:] My assumption that I have non-blue eyes must be false because it led to the conclusion that P3 commits suicide today, which did not happen. So, I must have blue eyes. Thus, I will commit suicide tomorrow.”
The next day arrives and P2 does not commit suicide (because unlike what P1 thinks that P2 thinks, P2 actually sees two blue-eyed people, which leads him to the same conclusions as P1). P1 sees that P2 is still alive and concludes that his assumption from the very beginning must be wrong and that he has indeed blue eyes.
The same process happens in P1, P2 and P3 and thus they all perish on the third day.
If we add a new person P4 with brown eyes, the process is the same, but there is no contradiction because the three other people do commit suicide on the third day.
After the traveler informed them, in a single moment, each islander analyzed the situation by repeatedly splitting it into mutually exclusive cases and sub-cases. In each step another person is assumed to have non-blue eyes (because assuming that somebody has blue eyes leads to deadlock). Eventually this led to the base case of everyone but one person having non-blue eyes. In this case, the traveler’s information does have a direct impact, because now we could conclude that the single blue-eyed person would kill himself. If we did not have it, we would not be able to continue the argument.
Now, with each new day, one link of that assumption chain is invalidated in reverse order. They fall like dominoes, where the first one fell because of the traveler’s statement. This continues until it reaches P1 himself on the (n-1)th day, when he realizes that he has blue eyes.
For example, in the beginning, P1 has derived something like “P1 has non-blue eyes => (P2 has non-blue eyes => P3 commits suicide on the next day)”. After the first day, P1 thinks: “Assume that I have non-blue eyes. Since P3 did not commit suicide, P2 must now think that he has blue eyes and thus, he will commit suicide.” So, P1’s new state of knowledge is “P1 has non-blue eyes => P2 commits suicide on the next day”. This in turns get invalidated on the second day, causing P1 to believe “P1 has blue eyes” and then right after, “P1 will commit suicide the next day”. Note that all of these changes occur only within the knowledge base of P1, they are not about something that actually happens!
It is interesting that the entire mental construct gets built up in one instant, but then is only deconstructed step-by-step as more and more information is presented each day. 2 Within this process, the information of “X will commit suicide” seems to propagate from the last member (e.g. P3) back to the first (P1).
This puzzle can be seen as an illustration of common knowledge.
In a group of agents, some information X is common knowledge if everybody knows X, everybody knows that everybody knows X, everybody knows that everybody knows that everybody knows X etc. X is nth order knowledge if everybody knows that “everybody knows that everybody knows … (n-1) times that X”. For example, if everybody knows X, then X is first-order knowledge. X is common knowledge if it is kth order knowledge for all n.
This concept connects to the puzzle in the following way. (1) If there are n blue-eyed people, then the fact “there is a blue-eyed person” becomes at most (n-1)th order knowledge right away. (2) However, to deduce their eye color, they need nth order knowledge. (3) The traveler’s address provides common knowledge, so in particular, nth order knowledge.
(1): If n = 2, then both people see one blue-eyed person, so there is first-order knowledge. However, they cannot know for sure that “everybody knows it” because it might be that they have brown eyes, which means that the other blue-eyed person does not see anyone else with blue eyes. For n = 3, there is second-order knowledge, because even if P1 assumes that he has brown eyes, P2 will still see the blue-eyed P3. However, there is no third-order knowledge. In the “worst case”, P1 assumes to have brown eyes himself and assumes that P2 assumes that P2 has brown eyes. But then, P3 would not see any blue-eyed people, which means that P2 (from P1’s perspective) cannot know that everybody knows. So, P1 cannot know that everybody knows that everybody knows.
(2): In the case of n = 2, both islanders have only first-order knowledge. What happens if it becomes second-order knowledge? Each of them thinks: “If I have brown eyes, then the other islander only sees brown-eyed people. But I know that he knows that there is at least one blue-eyed person. So he must conclude that it is him and commit suicide tomorrow”. When the other islander does not do the deed, they both realize that they have blue eyes.
This has an interesting consequence. What is the least information that the traveler has to give the islanders so that the same event happens? Answer: nth order knowledge. He could communicate that by informing each one in secret that “everybody knows that everybody knows (n-1 times) that there is a blue-eyed person”.
It is fascinating to see that a seemingly irrelevant and subtle piece of information can have such a dramatic effect!
(3): How does the traveler’s statement become common knowledge? Everybody knows since everybody heard him and everybody trusts him. Everybody knows that everybody knows, because any islander knows that any other islander heard him and trusts him (because everybody knows that everybody trusts him). And so forth.
What if the visitor had said “I have noticed that your people have either blue or brown eyes”? This implies that there is at least one islander with blue eyes and at least one with brown eyes and that all of them either have blue or brown eyes. Also, there now have to be at least 2 islanders.
Let (n,k) denote the situation in which the tribe consists of n blue-eyed and k brown-eyed people. If (1,1), then both know their color immediately and commit suicide on the first day. If n = k, then the same process as in the original case takes place in parallel and they die on the nth day. If n < k, then the blue-eyed people die on the nth day and the brown-eyed people (who know that there is only one color remains), die on the (n+1)th day.
A nuance here is that after this statement, all people in the tribe know that they are doomed. They know that they will eventually find out their eye color. But this is different to actually knowing which eye color they have, so they don’t die on the first day.
- In this solution, we assume that the islanders will do an analysis by cases. But we cannot guarantee that this is the only or the best possible line of reasoning. Hypothetically, there might be an argument that makes them kill themselves even sooner. So, technically, the solution here should be “On the nth day at the latest, the blue-eyed islanders kill themselves.” ↩
- One could argue that highly logical agents do not go through the hassle of the entire argument, but simply use the statement that was proved by induction. ↩