We consider a classic “paradox” where a simple inductive proof seems to clash with intuition. Though the proof makes clear that the naive intuition is wrong, it’s hard to pinpoint exactly where the intuition’s logical error is. After discussing the paradox at some length with my family, we came up with an angle of attack that gives an intuitive framework that both matches the math and makes the problem with the naive intuition clearer.

The situation is as follows. Dragons, as you probably already know, are a perfectly honest and rational species with color vision and either red or blue eyes. One hundred red-eyed dragons are on an island, sworn to a two-part pact:

  • they will not communicate with each other, look at reflections, or otherwise directly find out what color eyes they have, and
  • if any dragon can logically deduce some day that they have red eyes, then that dragon will leave the island the following night.

The dragons live for years on the island, each of them seeing ninety-nine red-eyed dragons but none of them able to logically deduce that they too have red eyes. One day, a perfectly honest visitor comes to the island, announces that at least one of the dragons has red eyes, and leaves.

If you haven’t heard this before, try to figure out before continuing: what happens?

On the one hundredth night after being told that at least one of them has red eyes, all the dragons leave the island!

Here’s the argument.

  • If there were exactly one dragon \(X\) with red eyes, they would have seen only blue eyes and deduced that they must be the one with red eyes, so \(X\) would leave on the first night following the announcement.
  • If there were exactly two dragons \(X\) and \(Y\) with red eyes, they would both stay the first night. The following day, each would see that the other hadn’t already left. \(X\) knows by the previous bullet point that if \(Y\) were the only dragon with red eyes, then \(Y\) would have left on the first night. This didn’t happen, so \(X\) deduces that they must also have red eyes. Symmetrically, so does \(Y\), and both leave on the second night.
  • More generally, if exactly \(k\) dragons have red eyes, then after \(k-1\) nights of no dragons leaving, each of them realizes that, if the other \(k-1\) red-eyed dragons were the only dragons with red eyes, they would have left on night \(k-1\). This didn’t happen, so they deduce that they must also have red eyes, and all \(k\) red-eyed dragons leave on night \(k\).

This is a pretty simple inductive argument, but there’s an apparent paradox: the announcement made by the visitor was something all of the dragons already knew! What difference does it make? The typical (and entirely correct) answer is that without the announcement, the first bullet point doesn’t hold. That bullet point is the crucial base case of the inductive argument each dragon uses to deduce they have red eyes. But even though I know how induction works, I find it very counterintuitive that this should matter, because every dragon sees at least two other red-eyed dragons and therefore knows they aren’t in the base case!

The rough reason that the base case matters, even though all the dragons know they aren’t in it, is that we have to not just consider what each dragon knows, but also what each dragon knows about what each other dragon knows… and what each dragon knows about what each other dragon knows about what each other dragon knows, and so on. I was able to figure things out for up to three red-eyed dragons, but after that there were too many cases to keep track of.

Following a common mathematical theme, to give ourselves better intuition about a complicated situation, we’re going to define a new concept and build intuition about that new concept instead of about the situation directly. Let us call a dragon \(k\)-aware for positive integer \(k\) under the following conditions.

  • A dragon is \(1\)-aware when they know at least one dragon has red eyes.
  • For \(k \geq 2\), a dragon is \(k\)-aware when they know every dragon is \((k-1)\)-aware.

For example, if only one dragon \(X\) has red eyes, then every other dragon is \(1\)-aware. If only two dragons \(X\) and \(Y\) have red eyes, then they are both \(1\)-aware and every other dragon is \(2\)-aware: not only do the other dragons know that \(X\) and \(Y\) have red eyes, but they know that each of \(X\) and \(Y\) can see the other, so they know that every dragon can see a red-eyed dragon. We can generalize this.

Theorem.

Before the visitor’s announcement, if a dragon can see at least \(k\) red-eyed dragons, they are \(k\)-aware, and if they can see at most \(k\) red-eyed dragons, they are not \((k+1)\)-aware.

Proof.

We prove each statement separately by induction.

  • If a dragon can see another red-eyed dragon, then they are \(1\)-aware.
  • If a dragon can see at least \(k \geq 2\) red-eyed dragons, then they know that every other dragon can see at least \(k-1\) red-eyed dragons. By the inductive hypothesis, they know every other dragon is \((k-1)\)-aware, so they are \(k\)-aware.
  • If a dragon sees no red-eyed dragons, then they are not \(1\)-aware.
  • If a dragon \(X\) can see at most \(k \geq 1\) red-eyed dragons, then because \(X\) must consider that they might have blue eyes, it is possible that each of those red-eyed dragons can see just \(k-1\) other red-eyed dragons. By the inductive hypothesis, \(X\) cannot know for sure that those red-eyed dragons are \(k\)-aware, so \(X\) is not \((k+1)\)-aware. \(\square\)

This theorem means that before the visitor’s announcement, the dragons are all \(99\)-aware. After the visitor’s announcement, the dragons become \(k\)-aware for every \(k \geq 1\) because of the public nature of the announcement: not only does everyone know that at least one dragon has red eyes, but everyone knows that everyone knows this, and everyone knows that everyone knows that everyone knows this, and so on. This makes all the difference.

Theorem.

If there are exactly \(k\) red-eyed dragons and they simultaneously become \(k\)-aware, they will leave \(k\) nights later.

Proof.

We prove only that the dragons that are supposed to leave do so at the right time, given that the other dragons stay. It’s not too hard to add the details to rigorously show that all the other dragons do indeed stay.

  • Suppose a dragon sees no red-eyed dragons but becomes \(1\)-aware. They immediately deduce they have red eyes because nobody else does, so they leave on the first possible night.
  • Suppose for some \(k \geq 2\) that a dragon \(X\) is \(k\)-aware and sees exactly \(k-1\) red-eyed dragons. By \(k\)-awareness, \(X\) knows that those red-eyed dragons are all \((k-1)\)-aware. \(X\) reasons that if they had blue eyes, then those red-eyed dragons would have each seen exactly \(k-2\) red-eyed dragons and, by the inductive hypothesis, would have left on night \(k-1\). Therefore, if this doesn’t happen, \(X\) can deduce that they must have red eyes and will leave on the next night, which is night \(k\). \(\square\)

The above proof is essentially the same as the initial argument, but the explicit definition and usage of \(k\)-awareness helped me (and, hopefully, you!) build better intuition for it.