# 2012 : WHAT IS YOUR FAVORITE DEEP, ELEGANT, OR BEAUTIFUL EXPLANATION?

Tisch University Professor of Computer Science, Cornell University

The Pigeonhole Principle

Certain facts in mathematics feel as though they contain a kind of compressed power—they look innocuous and mild-mannered when you first meet them, but they're dazzling when you see them in action. One of the most compelling examples of such a fact is the Pigeonhole Principle.

Here's what the Pigeonhole Principle says. Suppose a flock of pigeons lands in a group of trees, and there are more pigeons than trees. Then after all the pigeons have landed, at least one of the trees contains more than one pigeon.

This fact sounds obvious, and it is: there are simply too many pigeons, and so they can't each get their own tree. Indeed, if this were the end of the story, it wouldn't be clear why this is a fact that even deserves to be named or noted down. But to really appreciate the Pigeonhole Principle, you have to see some of the things you can do with it.

So let's move on to a fact that doesn't look nearly as straightforward. The statement itself is intriguing, but what's more intriguing is the effortless way it will turn out to follow from the Pigeonhole Principle. Here's the fact: Sometime in the past 4000 years, there have been two people in your family tree—call them A and B—with the property that A was an ancestor of B's mother and also an ancestor of B's father. Your family tree has a "loop", where two branches growing upward from B come back together at A—in other words, there's a set of parents in your ancestry who are blood relatives of each other, thanks to this relatively recent shared ancestor A.

It's worth mentioning a couple of things here. First, the "you" in the previous paragraph is genuinely you, the reader. Indeed, one of the intriguing features of this fact is that I can blithely make such assertions about you and your ancestors, despite the fact that I don't even know who you are. Second, the statement doesn't rely on any assumptions about the evolution of the human race, or the geographic sweep of human history. Here, in particular, are the only assumptions I'll need. (1) Everyone has two biological parents. (2) No one has children after the age of 100. (3) The human race is at least 4000 years old. (4) At most a trillion human beings have lived in the past 4000 years. (Scientists' actual best estimate for (4) is that roughly a hundred billion human beings have ever lived in all of human history; I'm bumping this up to a trillion just to be safe.) All four assumptions are designed to be as uncontroversial as possible; and even then, a few exceptions to the first two assumptions and an even larger estimate in the fourth would only necessitate some minor tweaking to the argument.

Now back to you and your ancestors. Let's start by building your family tree going back 40 generations: you, your parents, their parents, and so on, 40 steps back. Since each generation lasts at most 100 years, the last 40 generations of your family tree all take place within the past 4000 years. (In fact, they almost surely take place within just the past 1000 or 1200 years, but remember that we're trying to be uncontroversial.)