# Examples and applications of the pigeonhole principle

The Pigeonhole Principle (or Dirichlet's box principle) is a method introduced usually quite early in the mathematical curriculum. The examples where it is usually introduced are (in my humble experience) usually rather boring and not too deep.

It is well-known, however, that there are great and deep applications of it in research mathematics.

What applications of the pigeonhole principle would you consider in an "Introduction to proofs" course for university students? They should be non-trivial but accessible for undergraduate students, and an interchange between different mathematical fields is always welcome.

• related reading: (#1) (#2) (#3) – Alexander Gruber Apr 18 '14 at 1:06
• @AlexanderGruber: thank you. I should have included the first two in the question. – András Bátkai Apr 18 '14 at 6:56

• If $\gcd(a,b)=1$, there exists a multiplicative inverse for $a$ modulo $b$. (Otherwise, look at the $b-1$ multiples of $a$, namely $a,2a,3a,\dots,(b-1)a$. They must fall into congruence classes that aren't 0 or 1, but there are only $b-2$ of those.)
• $R(3,3)\leq 6$, and other Ramsey-style arguments
• Give any domino tiling of a $6\times 6$ checkerboard, there exists a way to split the board along some row or column that does not disturb the tiling.
• The Erdos-Szekeres result: Every sequence of length $ab+1$ contains a monotone increasing subsequence of length $a$ or a monotone decreasing subsequence of length $b$.
• "Lossless data compression algorithms cannot guarantee compression for all input data sets. In other words, for any lossless data compression algorithm, there will be an input data set that does not get smaller when processed by the algorithm, and for any lossless data compression algorithm that makes at least one file smaller, there will be at least one file that it makes larger." (source and proof: Wikipedia)

If this is in an intro to proofs course, I also recommend stating the following version and having the students prove it. It's a good example of a contradiction argument: "Given any $n$ real numbers, at least one of them is as large as their average."

• I'd prove it without contradicton (or pigeonhole principle): let $a_1$ be the largest of $a_1,\ldots,a_n$. Then the $a_1=a_1\cdot n/n\geq (a_1+\cdots+a_n)/n$. Actually, it's not obvious to me how you could even prove it using pigeonhole principle (though I see how you could prove it by contradiction, misguided as it seems to me). – tomasz Apr 19 '14 at 14:24

Dirichlet's theorem that an irrational number can be approximated to within $1/q^2$ for a sequence of rationals $p/q$ exemplifies this principle.

Application 1: Every rational number has a repeating decimal expansion.

Application 2: Each infinite decimal expansion has the property that there exists a $10^{100}$-length sequence of digits that is repeated infinitely often in the expansion.

Application 3: If $x$ is irrational, then at least two digits appear infinitely often in the decimal expansion of $x.$

• I believe it is possible to construct non-repeating sequences... – vonbrand Apr 18 '14 at 3:05
• @vonbrand, all three statements are correct. – Paul Draper Apr 18 '14 at 22:28
• @tomasz, "infinitely often" seems to me to be exactly equivalent to "infinitely many times" – Paul Draper Apr 19 '14 at 16:14
• @tomasz "infinitely often" is entirely standard jargon. – Gamma Function Apr 19 '14 at 23:29
• @GammaFunction: be that as it may, I still consider it misleading, especially considering we're talking about education. – tomasz Apr 20 '14 at 1:28

Problem

Each point in the plane is colored one of $n$ colors. Prove that there exists a rectangle whose four vertices are the same color.

Both the problem and the solution are very simple, yet those unfamilar with the Pigeonhole Principle would likely be at a complete loss to solve it.

Solution

Consider a grid of points with $n+1$ rows and $n^{n(n+1)/2}+1$ columns.

1. Since there are $n$ colors, by the Pigeonhole Principle, for each column there must be a pair of the $n+1$ grid points with the same color.
2. Each column has $\frac{n(n+1)}2$ possible positions for this same-colored pair. Since there are $n$ colors, each column has one of $n^{n(n+1)/2}$ possible same-colored pairs. By the Pigeonhole principle, two of the $n^{n(n+1)/2}+1$ columns have the same pair, forming a rectangle.

This problem works even better when explained visually.

The USA Mathematical Talent Search asked this problem for the case $n=3$.

If you want, you can extend this to a hypercube in $k$ dimensions.

• Should'nt your $n+1$ possible position be rather $n(n+1)/2$? This of course does not change the idea nor the statement. – Benoît Kloeckner Apr 19 '14 at 20:04
• @BenoîtKloeckner, thank you. I fixed it. There are ways to reduce the number of grid points needed (assumptions without loss of generality), but this way is easiest to understand. – Paul Draper Apr 20 '14 at 3:26
• I've been thinking about this a lot, and I'm confused by step 2. Shouldn't it be $\binom{n+1}{2}\cdot n$, i.e. multiplication not exponentiation? The idea is that you have $\binom{n+1}{2}$ "empty arrangements" of pairs of dots. Each one could be filled with one of the $n$ colors available (and then we don't even care what the colors of the other dots in the column are). Right? – Brendan W. Sullivan Sep 19 '14 at 14:25

Here is one application in introductory abstract algebra:

A finite integral domain is a field.

Show that among any $n + 1$ numbers out of $1, \ldots, 2n$ there are two that are relatively prime, and there is one that divides the other.