Theorem 11: the pigeonhole principle

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 n+1 pigeons into n pigeonholes, then at least one pigeonhole will contain at least two pigeons.

More generally, if one puts kn+1 pigeons into n pigeonholes, then at least one pigeonhole will contain at least k+1 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, k+1) 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 n pigeons in total.  So if we have n+1 pigeons, then at least one pigeonhole contains at least two pigeons.

A very similar argument shows the more general result about kn+1 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 rationalsThe square root of 2 is irrational, but is it close to a rational?  That’s a rather vague question.  We can approximate \sqrt{2} arbitrarily well by rationals: just take the decimal expansion of \sqrt{2} 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 \sqrt{2} pretty well by a rational with a pretty small denominator?  What if we replace \sqrt{2} 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 \alpha be an irrational number, and let N be a positive integer.  Then there is a rational p/q such that the denominator q is between 1 and N and such that |\alpha - \frac{p}{q}| \leq \frac{1}{qN}.

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 |\alpha - \frac{p}{q}| \leq \frac{1}{qN} is to say that q\alpha is within 1/N of an integer (and we then choose p to be that integer).  So we’d like to show that there’s some q, with 1\leq q\leq N, such that q\alpha is within 1/N 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 [0,1) for the set of all real numbers less than 1 and at least 0.  Split this interval into N subintervals, each of length 1/N: [0, \frac{1}{N}), [\frac{1}{N}, \frac{2}{N}), …, [\frac{N-1}{N},1).  These subintervals will be our pigeonholes.

We’re going to use the fractional parts of some numbers.  The fractional part of a number x is “the bit after the decimal point”, so it always lies in the interval [0,1).  We write \{x \} for the fractional part of x.  Our pigeons will be the N+1 numbers 0, \{\alpha\}, \{2\alpha\}, \{3\alpha\}, …, \{N\alpha\}.

Now the pigeonhole principle tells us that two of these numbers, say \{r\alpha\} and \{s\alpha\} (with r < s), lie within the same subinterval.  That immediately means that (s-r)\alpha is within 1/N of an integer.  Now define q=s-r.  Then certainly 1\leq q\leq N, and q\alpha is within 1/N 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, \sqrt{2} 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.


3 Responses to “Theorem 11: the pigeonhole principle”

  1. Theorem 20: the Bolzano-Weierstrass theorem « Theorem of the week Says:

    […] number of terms in total, which would be absurd.  (This is rather like the argument used in the pigeonhole principle.)  If contains infinitely many of the terms, put and (so this becomes our new interval).  If […]

  2. adi Says:

    Is there any application of pigeonhole in real life, like in the office, hospital or supermarket?

  3. Number Theory: Lecture 18 « Theorem of the week Says:

    […] Proposition 56 (Dirichlet): Let be a real number and let be a natural number.  Then there is a rational with such that .  We saw that we could prove this quite easily using the pigeonhole principle. […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: