The pigeonhole principle is a fairly simple idea to understand, and is extremely useful — mathematicians use it all the time. Despite that, it seems not to be mentioned in most schools (in the UK). This week, I’d like to tell you about it, and to give a nice application. My understanding is that the pigeonhole principle was first stated by Dirichlet (although he didn’t call it that!), who used it to prove a result about Diophantine approximation — this is the application that I’d like to describe here. The pigeonhole principle is sometimes called Dirichlet’s box principle.
Theorem (the pigeonhole principle) If one puts pigeons into pigeonholes, then at least one pigeonhole will contain at least two pigeons.
More generally, if one puts pigeons into pigeonholes, then at least one pigeonhole will contain at least pigeons.
It’s important to note what the theorem does not say. It might be that just one pigeonhole contains all the pigeons — they don’t have to be evenly spread out. It might be that several pigeonholes contain multiple pigeons. All the theorem says is that at least one pigeonhole contains at least two (or, in the general case, ) pigeons.
I hope that this statement seems fairly obvious to you. Its power is not that it is a deep and profound result in itself, but rather that it has many applications. Nonetheless, one still needs to prove it. Fortunately, that’s not too difficult — the hardest thing is possibly accepting that it does indeed need proof! If you ask yourself why the pigeonhole principle is true, I think that you are very likely to hit upon a proof for yourself.
Indeed, how could it possibly not be true? Suppose that each pigeonhole contains at most one pigeon (so either it contains one pigeon, or it is empty). Then there are at most pigeons in total. So if we have pigeons, then at least one pigeonhole contains at least two pigeons.
A very similar argument shows the more general result about pigeons.
Sometimes it’s actually easier to use the idea of the proof than to quote the result. It’s all the same idea, though.
As I mentioned above, Dirichlet used this principle to prove a result about approximating irrational numbers by rationals. The square root of 2 is irrational, but is it close to a rational? That’s a rather vague question. We can approximate arbitrarily well by rationals: just take the decimal expansion of and chop it off at some point (ignore all the digits to the right of that point). That gives a rational (it has a finite decimal expansion), and we can make the error as small as we like by choosing the point at which we chop the decimal. But in order to get a good approximation using this method, we need a rational with large denominator.
So here’s a more refined version of the question. Can we approximate pretty well by a rational with a pretty small denominator? What if we replace by another irrational? There’s a whole area of research on this sort of question, and lots of very interesting results. Dirichlet’s theorem is a relatively simple one, and that’s all that I’ll mention today. (I hope to come back to the subject of approximating irrationals by rationals in a future theorem of the week.)
Theorem (Dirichlet) Let be an irrational number, and let be a positive integer. Then there is a rational such that the denominator is between 1 and and such that .
Here’s the proof. As you will by now have gathered, the plan is to use the pigeonhole principle. Another way of expressing the conclusion is to say that is within of an integer (and we then choose to be that integer). So we’d like to show that there’s some , with , such that is within of an integer. We need some pigeonholes and some pigeons.
We’re going to use the interval from 0 to 1, including 0 but not 1. Mathematicians have notation for this interval: we write for the set of all real numbers less than 1 and at least 0. Split this interval into subintervals, each of length : , , …, . These subintervals will be our pigeonholes.
We’re going to use the fractional parts of some numbers. The fractional part of a number is “the bit after the decimal point”, so it always lies in the interval . We write for the fractional part of . Our pigeons will be the numbers , , , , …, .
Now the pigeonhole principle tells us that two of these numbers, say and (with ), lie within the same subinterval. That immediately means that is within of an integer. Now define . Then certainly , and is within of an integer, as we wanted.
As I say, there are more results along these lines, and they are more precise about how well various irrational numbers can be approximated by rationals. (For example, is actually quite hard to approximate by rationals with small denominators.) But they’ll have to wait for a future post!
There are some more applications of the pigeonhole principle on the Wikipedia page.