The Tale of the Green-Eyed Dragons
Here's a mind-blowing logic puzzle that my math professor shared last week.
One day, however, a visitor arrives to the tribe. On the day she arrives – we will call this day 1 – she remarks, "I see a dragon with green eyes." The visitor leaves later that day. At the end of day 1, no dragon in the tribe performs the ritual. At the end of the next day (day 2), no one performs the ritual. In fact, after the visitor leaves, the dragons continue to live in peace for 99 days. On day 100, however, something remarkable happens. All 100 green-eyed dragons commit ritual suicide on day 100. Why?
Suppose that the tribe has just 1 dragon with green eyes. The visitor arrives to the tribe and says on day 1, "I see a dragon with green eyes." The green-eyed dragon looks around, sees that there is no other dragon that the visitor could be talking about, and deduces that he must have green eyes. Therefore, if there is only 1 green-eyed dragon in the tribe, then that dragon will perform the ritual on day 1.
Let's suppose now that the tribe has 2 dragons with green eyes. This case isn't required for the proof to work, but let's do it for the sake of identifying a pattern. The visitor arrives to the tribe and says on day 1, "I see a dragon with green eyes." Both of the green-eyed dragons see one other dragon with green eyes. Neither dragon knows for sure yet what his own eye color is, so they do not perform the ritual on day 1. However, they both know that if there is only 1 green-eyed dragon in the tribe, then that dragon will perform the ritual on day 1 (this is what we proved in the last paragraph; see the bolded sentence). When day 1 passes and they notice that no one committed suicide, then both of the green-eyed dragons will know that there is more than one dragon with green eyes. Imagine you are one of the green-eyed dragons. You know that there is more than one dragon with green eyes, but you can only see one other dragon besides yourself with green eyes. You have to deduce that you have green eyes. Therefore, if there are 2 green-eyed dragons in the tribe, then both dragons will perform the ritual on day 2.
Do you see the pattern?
Let's assume, just for a second, that if there are exactly n green-eyed dragons, then they will all perform the ritual on day n. n is a positive whole number. Consider, now, a tribe with n + 1 green-eyed dragons. The visitor comes and announces on day 1 that she sees a green-eyed dragon. Imagine you are one of the green-eyed dragons – you look around, and you can see n green-eyed dragons. Based on our assumption, if there were only n green-eyed dragons (i.e. you are the only dragon without green eyes), then all the green-eyed dragons should perform the ritual on day n. However, on day n + 1, no one has committed suicide. Thus, you have to conclude that the other dragons can see more than n green-eyed dragons, but since you can only see n green-eyed dragons, you must deduce that you are the one extra green-eyed dragon the others are seeing. Therefore, if it is true that n green-eyed dragons will perform the ritual on day n, then it will also be true that n + 1 green-eyed dragons will perform the ritual on day n + 1.
Think about what that statement means for a second, and think about how logically powerful this conclusion is. We have already proven that 1 green-eyed dragon will perform the ritual on day 1 (the bolded sentence from the first paragraph), so if we let n = 1, it must automatically be the case that 2 green-eyed dragons will perform the ritual on day 2. And if it is case that 2 green-eyed dragons will perform the ritual on day 2, then if we let n = 2, it must automatically be the case that 3 green-eyed dragons will perform the ritual on day 3. And so and and so forth as n grows larger and larger towards infinity. It's like dominoes: the truth of the statement for n automatically implies the truth of the statement for n + 1, and since we've proven the statement for n = 1, then the statement must be true for all n ≥ 1. Therefore, if there are n green-eyed dragons, then all n green-eyed dragons will perform the ritual on day n.
This, of course, means that if n is 100, then all 100 green-eyed dragons will perform the ritual on day 100.
First objection: The visitor did not give the dragons any new information.
After all, all 100 green-eyed dragons could each also see at least one other dragon with green eyes. The claim is that the visitor's remark, "I see a dragon with green eyes", did not share anything new that the dragons didn't already know. This isn't true. The visitor did share something, but it is a bit more subtle than you might think. Although every dragon already knew there was at least one dragon with green eyes, what every dragon did not know beforehand was that every other dragon also knows that there is at least one dragon with green eyes.
It may help to reduce the problem a bit to see what I mean: consider a tribe with 2 green-eyed dragons – we'll call them Dragon A and "me". I can see one other dragon with green eyes, but the question is, "Do I know that Dragon A knows there is at least one green-eyed dragon?" No. I don't know what my own eye color is, so for all I know, Dragon A could be seeing one dragon with blue eyes. The visitor coming to the island gives all dragons the information that there is at least one green-eyed dragon, so now all dragons know that everybody knows that there is at least one green-eyed dragon.
As we progress to 3 green-eyed dragons – let's call them Dragon A, Dragon B, and "me" – the question becomes, "Do I know that Dragon A knows that Dragon B knows there is at least one green-eyed dragon?" (confusing, I know!) The answer is no because for all I know, I have blue eyes, which means that I think Dragon A might be seeing one blue-eyed dragon (me) and one green-eyed dragon (Dragon B). However, if Dragon A thinks that, then it's possible that Dragon A thinks that Dragon B can't see any green-eyed dragons, because Dragon A doesn't know what his eye color is either, so if he thinks his eye color is blue, and if my eye color is blue, then he will think that it's possible Dragon B can't see any green-eyed dragons. The visitor comes, and now all dragons know that everyone knows there is at least one green-eyed dragon.
As we progress to 100 dragons, the way my instructor described it was "100-level nested thinking", i.e. "Do I know that Dragon 1 knows that Dragon 2 knows that Dragon 3 knows ... that Dragon 98 knows that Dragon 99 knows that there is at least one green-eyed dragon?"
Second objection: In your proof, you assume what you are trying to prove.
In the second half of the solution, I wrote:
The reason why I make the assumption is to show that if the statement holds for a given n, then it must also hold for n + 1. Note that my assumption does not have to be true for this to hold. If, in fact, the statement does not hold for n dragons, then we know nothing about n + 1 dragons. What I proved, however, was that if the claim does hold for n dragons, then it must also hold for n + 1 dragons. This fact is combined with the fact that the claim holds for 1 dragon to show that it holds for all numbers of dragons.
Problem
A long time ago, there lived a tribe of 100 green-eyed dragons. These dragons had a rule: if any dragon in the tribe deduces what the color of his eyes was, then that dragon must commit ritual suicide by the end of that day. Aside from this, the dragons lived peacefully. Although each dragon could see the eye color of every other dragon, no dragon was cruel enough to discuss eye colors with other dragons. For all each dragon knew, he or she could be the one dragon that had blue eyes among 99 green-eyed dragons.One day, however, a visitor arrives to the tribe. On the day she arrives – we will call this day 1 – she remarks, "I see a dragon with green eyes." The visitor leaves later that day. At the end of day 1, no dragon in the tribe performs the ritual. At the end of the next day (day 2), no one performs the ritual. In fact, after the visitor leaves, the dragons continue to live in peace for 99 days. On day 100, however, something remarkable happens. All 100 green-eyed dragons commit ritual suicide on day 100. Why?
Solution
The proof is by mathematical induction on the number of green-eyed dragons.Suppose that the tribe has just 1 dragon with green eyes. The visitor arrives to the tribe and says on day 1, "I see a dragon with green eyes." The green-eyed dragon looks around, sees that there is no other dragon that the visitor could be talking about, and deduces that he must have green eyes. Therefore, if there is only 1 green-eyed dragon in the tribe, then that dragon will perform the ritual on day 1.
Let's suppose now that the tribe has 2 dragons with green eyes. This case isn't required for the proof to work, but let's do it for the sake of identifying a pattern. The visitor arrives to the tribe and says on day 1, "I see a dragon with green eyes." Both of the green-eyed dragons see one other dragon with green eyes. Neither dragon knows for sure yet what his own eye color is, so they do not perform the ritual on day 1. However, they both know that if there is only 1 green-eyed dragon in the tribe, then that dragon will perform the ritual on day 1 (this is what we proved in the last paragraph; see the bolded sentence). When day 1 passes and they notice that no one committed suicide, then both of the green-eyed dragons will know that there is more than one dragon with green eyes. Imagine you are one of the green-eyed dragons. You know that there is more than one dragon with green eyes, but you can only see one other dragon besides yourself with green eyes. You have to deduce that you have green eyes. Therefore, if there are 2 green-eyed dragons in the tribe, then both dragons will perform the ritual on day 2.
Do you see the pattern?
Let's assume, just for a second, that if there are exactly n green-eyed dragons, then they will all perform the ritual on day n. n is a positive whole number. Consider, now, a tribe with n + 1 green-eyed dragons. The visitor comes and announces on day 1 that she sees a green-eyed dragon. Imagine you are one of the green-eyed dragons – you look around, and you can see n green-eyed dragons. Based on our assumption, if there were only n green-eyed dragons (i.e. you are the only dragon without green eyes), then all the green-eyed dragons should perform the ritual on day n. However, on day n + 1, no one has committed suicide. Thus, you have to conclude that the other dragons can see more than n green-eyed dragons, but since you can only see n green-eyed dragons, you must deduce that you are the one extra green-eyed dragon the others are seeing. Therefore, if it is true that n green-eyed dragons will perform the ritual on day n, then it will also be true that n + 1 green-eyed dragons will perform the ritual on day n + 1.
Think about what that statement means for a second, and think about how logically powerful this conclusion is. We have already proven that 1 green-eyed dragon will perform the ritual on day 1 (the bolded sentence from the first paragraph), so if we let n = 1, it must automatically be the case that 2 green-eyed dragons will perform the ritual on day 2. And if it is case that 2 green-eyed dragons will perform the ritual on day 2, then if we let n = 2, it must automatically be the case that 3 green-eyed dragons will perform the ritual on day 3. And so and and so forth as n grows larger and larger towards infinity. It's like dominoes: the truth of the statement for n automatically implies the truth of the statement for n + 1, and since we've proven the statement for n = 1, then the statement must be true for all n ≥ 1. Therefore, if there are n green-eyed dragons, then all n green-eyed dragons will perform the ritual on day n.
This, of course, means that if n is 100, then all 100 green-eyed dragons will perform the ritual on day 100.
Replies to common objections
This proof was first explained to me by Dr. Satish Rao, a professor of computer science at UC Berkeley, who co-taught the course Discrete Mathematics and Probability Theory, which I audited in the spring of 2018. It was then reintroduced to me in the summer of 2018, when I took the course for real, taught by Sinho Chewi, an applied mathematics Ph.D. student at MIT. There are a couple common objections to the proof, the responses to which may help you better understand the proof.First objection: The visitor did not give the dragons any new information.
After all, all 100 green-eyed dragons could each also see at least one other dragon with green eyes. The claim is that the visitor's remark, "I see a dragon with green eyes", did not share anything new that the dragons didn't already know. This isn't true. The visitor did share something, but it is a bit more subtle than you might think. Although every dragon already knew there was at least one dragon with green eyes, what every dragon did not know beforehand was that every other dragon also knows that there is at least one dragon with green eyes.
It may help to reduce the problem a bit to see what I mean: consider a tribe with 2 green-eyed dragons – we'll call them Dragon A and "me". I can see one other dragon with green eyes, but the question is, "Do I know that Dragon A knows there is at least one green-eyed dragon?" No. I don't know what my own eye color is, so for all I know, Dragon A could be seeing one dragon with blue eyes. The visitor coming to the island gives all dragons the information that there is at least one green-eyed dragon, so now all dragons know that everybody knows that there is at least one green-eyed dragon.
As we progress to 3 green-eyed dragons – let's call them Dragon A, Dragon B, and "me" – the question becomes, "Do I know that Dragon A knows that Dragon B knows there is at least one green-eyed dragon?" (confusing, I know!) The answer is no because for all I know, I have blue eyes, which means that I think Dragon A might be seeing one blue-eyed dragon (me) and one green-eyed dragon (Dragon B). However, if Dragon A thinks that, then it's possible that Dragon A thinks that Dragon B can't see any green-eyed dragons, because Dragon A doesn't know what his eye color is either, so if he thinks his eye color is blue, and if my eye color is blue, then he will think that it's possible Dragon B can't see any green-eyed dragons. The visitor comes, and now all dragons know that everyone knows there is at least one green-eyed dragon.
As we progress to 100 dragons, the way my instructor described it was "100-level nested thinking", i.e. "Do I know that Dragon 1 knows that Dragon 2 knows that Dragon 3 knows ... that Dragon 98 knows that Dragon 99 knows that there is at least one green-eyed dragon?"
Second objection: In your proof, you assume what you are trying to prove.
In the second half of the solution, I wrote:
Let's assume, just for a second, that if there are exactly n green-eyed dragons, then they will all perform the ritual on day n. n is a positive whole number.The claim is that this assumption is the conclusion that I intend to prove. Assuming the truth of the conclusion in the premises of an argument for that conclusion is a serious logical fallacy called begging the question. To answer this objection, let's be clear exactly what we are trying to prove: we are trying to prove that for all positive whole numbers n, if there are exactly n green-eyed dragons, then they will all perform the ritual on day n. This is different from my assumption here: my assumption is that for a given n, if there are exactly n green-eyed dragons, then they will all perform the ritual on day n. Do you see the difference? The claim I intend to prove is that all positive whole numbers will satisfy the statement, whereas my assumption is that the statement holds for a given positive whole number n.
The reason why I make the assumption is to show that if the statement holds for a given n, then it must also hold for n + 1. Note that my assumption does not have to be true for this to hold. If, in fact, the statement does not hold for n dragons, then we know nothing about n + 1 dragons. What I proved, however, was that if the claim does hold for n dragons, then it must also hold for n + 1 dragons. This fact is combined with the fact that the claim holds for 1 dragon to show that it holds for all numbers of dragons.