Hey, this is my second post. Recently I saw a very interesting puzzle online while reading the A Practical Guide for Quantitative Finance Interview (also high recommended by QuantNet). I find the puzzle amazing and potentially to be a quant interview question (though a little bit tough but intuitive once we find the pattern), so I feel like sharing with you.
The puzzle itself is proposed by Terence Tao in his blog, mathematician in UCLA, Fields Price winner. It is a hard one requiring serious logic induction. Ready? Let’s get your brain teased! XD
Question
There is an island upon which a tribe resides. The tribe consists of 1000 people, 100 of which are blue-eyed and 900 of which are brown-eyed. Yet, their religion forbids them to know their own eye color, or even to discuss the topic; thus, one resident can see the eye colors of all other residents but has no way of discovering his own (there are no reflective surfaces). If a tribesperson does discover his or her own eye color, then their religion compels them to commit ritual suicide at noon the following day in the village square for all to witness. All the tribespeople are highly logical, highly devout, and they all know that each other is also highly logical and highly devout.
One day, a blue-eyed foreigner visits to the island and wins the complete trust of the tribe. One evening, he addresses the entire tribe to thank them for their hospitality. However, not knowing the customs, the foreigner makes the mistake of mentioning eye color in his address, mentioning in his address “how unusual it is to see another blue-eyed person like myself in this region of the world”.</b>
What effect, if anything, does this faux pas have on the tribe?
First Glimpse
The puzzle looks like a paradise in the first glimpse, there are two argues as the following:
Argument I: The foreigner has no effect, because his comments do not tell the tribe anything that they do not already know (everyone in the tribe can already see that there are several blue-eyed people in their tribe).
Argument II: 100 days after the address, all the blue eyed people commit suicide. This is proven as a special case of the Proposition
Proposition: Suppose that the tribe had n blue-eyed people for some positive integer n. Then n days after the traveller’s address, all n blue-eyed people commit suicide.
Analysis
The key to solve this puzzle is to understand the logic concept of Common Knowledge, the first intuition tells us that the foreigner tells something that everyone knows, so it should have no effect. While the concept Everyone knows does not imply Everyone knows that every knows, you see the difference?
Common Knowledge is a special kind of knowledge for a group of agents. There is common knowledge of p in a group of agents G when all the agents in G know p, they all know that they know p, they all know that they all know that they know p, and so on ad infinitum.
We all heard the story of The Emperor’s New Clothes from Hans Christian Andersen, which turns out to be a typical example to illustrate the concept: In the story, everyone does not see the new clothes on the emperor while no body knows whether others can see or not, so the can’t see the new clothes is not a common knowledge in the context, only after one child shouts out “That emperor is naked!”, the knowledge spreads out among people, it becomes a common knowledge since now everyone knows that they all can’t see the new clothes.
Before we enter into the formal proof, think about it carefully and try to solve it by your own!
- TIP: start from the base case where only 1 or 2 out of 1000 have(s) blue eyes.
Proof
Now let’s start from the simplest case, what if only 1 or 2 out of 1000 islanders have(s) blue eyes?
Case 1: If you consider the case of just one blue-eyed person on the island, you can show that he obviously commits suicide the first night, because he knows he’s the only one the foreigner could be talking about. He looks around and sees no one else, and knows he should commit suicide. So: [THEOREM 1]: If there is one blue-eyed person, and thus commits suicide on the next day
Case 2: If there are two blue-eyed people, they will each look at the other. They will each realize that “if I don’t have blue eyes [HYPOTHESIS 1], then that guy is the only blue-eyed person”. And if he’s the only person, by THEOREM 1 he will leave tonight.” They each wait and see, and when neither of them commit suicide the first night, each realizes “My HYPOTHESIS 1 was incorrect. I must have blue eyes.” And each commits suicide the second night.
General: This induction can continue all the way up to THEOREM 99, which each person on the island in the problem will of course know immediately. Then they’ll each wait 99 days, see that the rest of the group hasn’t committed suicide anywhere, and on the 100th night, they all kill themselves.
When there are n people who have blue eyes, then they should all commit suicide on the n-th night. We can prove that rigorously by Mathematical Induction, but to give an “guessed” answer and underlying analysis is fairly enough if this was an interview question.
I found a version of Mathematical Induction by formal logic syntax on Reddit Here, and post it as below:
==BASE CASE==
TO PROVE: F(1) = G(1). If exactly one person had blue eyes, he would leave on day one1 GIVEN at least one person on the island has blue eyes (from the oracle, who speaks only truth)
2 BASE HYPOTHESIS exactly one person has blue eyes
3 BY EXCLUSION AND 2 The person with blue eyes sees no one else with blue eyes
4 BY ELIMINATION AND 3 AND 1 The person with blue eyes concludes that he must have blue eyes
5 QED: If exactly one person had blue eyes, he would leave on day one. F(1) = G(1)==INDUCTIVE CASE==
TO PROVE: If F(n) = G(n) then F(n+1) = G(n+1). (If n people have blue eyes, they will leave on day n) implies (If n+1 people have blue eyes, they will leave on day n+1)6 GIVEN No one leaves until he knows he has blue eyes
7 ASSUMING n+1 people have blue eyes
8 INDUCTIVE HYPOTHESIS n people with blue eyes will leave on day n
9 BY EXCLUSION AND 7 Each person with blue eyes will see n people with blue eyes
10 BY 6 AND 7 AND 8 No one leaves on day n
11 BY 8 AND 10 The number of people with blue eyes cannot be n
12 BY ELIMINATION AND 9 AND 11 Each person with blue eyes reasons that he must have blue eyes (to make the total not equal to n)
13 QED: (If n people have blue eyes, they will leave on day n) implies (If n+1 people have blue eyes, they will leave on day n+1). If F(n) = G(n) then F(n+1) = G(n+1)==INDUCTIVE CONCLUSION==
14 BY INDUCTION AND 5 AND 13 x people with blue eyes will leave on day x
Variants
The question has two amazing variants originally posted by Terence Tao:
Variant 1: If the foreigner realizes his mistake on the next day his speech, is there a way the foreigner can reduce the number of casualties?
Variant 2: What if the foreigner only realizes his mistake several days after his speech?
The variants will not be discussed in this post, while I may include them in the future.
Further Thoughts
A few words could bring such dramatic power, this is the power of Sharing Knowledge. Such concept could also be introduced into an interesting topic:
Why We Need to Express Love (“我们为什么要表白?”).
Before we express love, we feel that we like this girl and also from the interaction, we believe that this girl is also interested in me, the same feeling comes from the girl as well. But this is not
Common Knowledge, i.e. we love each other deeply while neither of us knows the other’s heart.After we express love, “We love each other” becomes common knowledge, (i.e. we both know we love each other), so we end up together happily.
I will also post puzzles I find interesting in the future, they provide wonderful samples to prepare Quant interview questions and themselves are intriguing. If you like this post, share it with your friends! XD
