Truths that are self-evident tend to be the ones we take for granted. There is air that we breathe, there is the sun, there are streams and fields, and a good nature poem frames these truths in such a way that you say, yes: there is air that we breath, there is the sun, there are streams and fields, and isn't that just something else? You already knew whatever the poem told you, but seeing it written down can be a gratifying, affirming experience.

In this sense, the pigeonhole principle is a poem, and Johann Dirichlet is a poet. I don't think it would be fair to say that Dirichlet "invented" the pigeonhole principle, just as a poet does not invent the sunshine, but he wrote it down so as to be applicable and appreciable. Let's see it first by way of an example.

Advertisement

Suppose you have ten pigeons, and you need to put them in nine holes, as you, a crazy person, are wont to do. There are many ways to do this: You could put all ten in the same hole. You could put five in one hole, and four in another. You could put two in one hole and one each in the other eight.

But how many ways can't you do it? Though it seems absurd to even write down (and maybe that's why no one did until the 19th century), you cannot put each pigeon in its own hole. Said differently: If you have ten pigeons, and you put them in nine holes, there must be at least one hole containing two or more pigeons.

This is obvious. And, in a more general form, it is one of the most powerful ideas in all of mathematics: If you have N objects, and you need to put them in M boxes, and N is bigger than M, then at least one box must contain two or more objects.

Advertisement

I know, with absolute certainty, that two people who have visited Deadspin in the last month paid the same amount of money (rounded to the nearest dollar) for their cars. This seems reasonable; there are only so many possible car prices, and Deadspin gets a ton of readers, so it at least seems unlikely that every single reader somehow paid a unique price for their vehicle. But how could I possibly know that, for sure, without reviewing some sort of list of prices paid? (Hint: It's the pigeonhole principle. That's how I know.)

You see, according to this article (by the NY Daily News, so maybe I ought to retract 'absolute certainty'), the most expensive car in the world costs $3.9 million. So I'm going to go ahead and make the fairly safe assumption that no one paid more than that for their car. This gives us 3,900,001 possible nearest-whole-dollar car prices (including $0, because why not).

Now, according to this fairly official-looking website, more than 4.5 million people visited Deadspin last month. Observe: 4,500,000 is a bigger number than 3,900,001. More people read Deadspin than the number of possible car prices, and so, by the pigeonhole principle, two Deadspinners must have cars that cost the same amount of money.

Have there been two professional baseball players that finished their careers with the same number of total bases? Probably, right? I mean, what about guys who played one game ever and struck out four times - there have probably been two such players, and they both finished with zero! But why assume that? Why settle for "probably" when you can simply observe that Hank Aaron has the career record in total bases with 6856, and there have definitely been more than 6856 pro baseball players in history, and so by the pigeonhole principle (pigeons = players, holes = # of career bases) two players must have finished with the same number?

This is the beauty of the pigeonhole principle. It allows us to move from "probably" to "certainly," from "come on, that's gotta be true" to "oh, wow, that has literally got to be true," by way of a trivial observation, provided you can actually identify the 'pigeons' (objects) and the 'holes' (boxes). This was fairly obvious in the above settings - settings described in the English language, concerning topics about which we all have a fair amount of intuition - but it's not always so easy.

For example: Say n is some natural number. From the set of numbers {1, 2, 3, ..., 2*n}, if n + 1 numbers are selected, there will always be two numbers whose greatest common divisor is 1. I want to use the pigeonhole principle to prove this (indeed, I invite the reader to try to prove it without some form of the pigeonhole principle). It makes sense to think that the numbers should be the 'objects,' but then, what are the boxes? Well, we should choose the boxes in a clever way, so that they satisfy the following two properties:

Advertisement

1. that making n + 1 choices ensures that we must have chosen two from the same box, and

2. that any two numbers from the same box have greatest common divisor equal to 1.

Can this be done? Yes! It is a fact that for any natural number x, the greatest common divisor of x and x+1 is always 1. (This is easy to see: If two numbers are divisible by two, they're both even, so their difference is at least two. If they're divisible by three, they're both multiples of three, so their difference is at least three, etc.) So split the set {1, 2, ..., 2*n} into subsets: {1, 2}, {3, 4}, ..., {2*n - 1, 2n}. There are n such subsets, and the two numbers in the same subset have greatest common divisor equal to one. Thus, when we choose n + 1 numbers, the pigeonhole principle tells us that we must choose two from the same subset, and the (totally not obvious, completely unintuitive) claim follows immediately.

Advertisement

What just happened is an illustration of a common theme in mathematics: When we can't solve a problem, we simply change it into a different problem. Maybe we can't prove that something is true, but we can prove that its truth is equivalent to the truth of something else, something easier to think about. We can't say much about the GCDs of randomly chosen elements of some arbitrarily large set, but by rephrasing the problem in the language of the pigeonhole principle, we can mess around with these notions of 'objects' and 'boxes,' and hey, look, we proved what we wanted, and it wasn't hard at all.

I had never realized these things about nighttime, Mr. Whitman, but when you put it like that, I see that they were obvious all along.