What is your favorite application of the Pigeonhole Principle?

The pigeonhole principle states that if $n$ items are put into $m$ "pigeonholes" with $n > m$, then at least one pigeonhole must contain more than one item.

I'd like to see your favorite application of the pigeonhole principle, to prove some surprising theorem, or some interesting/amusing result that one can show students in an undergraduate class. Graduate level applications would be fine as well, but I am mostly interested in examples that I can use in my undergrad classes.

There are some examples in the Wikipedia page for the pigeonhole principle. The hair-counting example is one that I like... let's see some other good ones!

Thanks!

Solution 1:

As the wikipedia article describes, Dirichlet's approximation theorem is a foundational result in diophantine approximation. For a real number $x$, let $\|x\|$ denote the distance from $x$ to its closest integer. Then the theorem states that for any irrational number $\alpha$, there exists infinitely many $q \gt 0$ such that $$ \| q\alpha \| \leqslant \frac{1}{q}. $$ This theorem is a simple consequence of the pigeonhole principle, and I was very surprised on seeing the proof. You can find the proof in robjohn's answer to the question: Approximation of irrationals by fractions.

In words, this theorem says that we can approximate the irrationals as closely as we want (in the sense of $\| q \alpha \|$) if we are allowed to pick a large enough $q$. This may not sound that surprising at first, but it becomes striking when one compares it to rational case.

Suppose $\alpha = a/b$ where $a$ and $b$ are integers and $b \geqslant 1$. We want to know how well $\alpha$ can be approximated using other rationals, since otherwise the problem is trivial. So fix $p/q \neq \alpha = a/b$. Rearranging, $qa - pb$ is nonzero; since it is also an integer, $|qa - pb|$ must be at least $1$. Thus, $$ |q\alpha - p| = \frac{|qa - pb|}{b} \geqslant \frac{1}{b}. $$ In particular, if $q \alpha$ is not an integer, then $\| q \alpha \| \geqslant \frac{1}{b}$, which is bounded away from zero, irrespective of $q$.

Thus, in a precise sense, the irrational numbers can be better approximated using rationals than the rational numbers themselves! (Of course, as stated previously, in the rational case, we do not count "approximating" the number by itself.)

Solution 2:

One fairly interesting result is that it is impossible to create a lossless data compression algorithm that shortens every input file. If it is lossless, it must actually make some files longer. The proof of this is outlined very nicely on wikipedia.