20
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ related reading: (#1) (#2) (#3) $\endgroup$
    – Alexander Gruber
    Apr 18, 2014 at 1:06
  • $\begingroup$ @AlexanderGruber: thank you. I should have included the first two in the question. $\endgroup$
    – András Bátkai
    Apr 18, 2014 at 6:56

6 Answers 6

Reset to default
19
$\begingroup$
  • 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."

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$
    – tomasz
    Apr 19, 2014 at 14:24
  • $\begingroup$ On the gcd example, you need to assume that $\gcd(a, b) = 1$ implies that $na$ is not congruent to $0$ modulo $n$ for $n = 1, 2, \ldots, (b - 1)$. However, I think that proving this relies on Bézout's identity (i.e. here if $\gcd(a, b) = 1$ then $ax + by = 1$ for some integers $x$ and $y$) and once you've got that you've got a direct proof of the existence of a multiplicative for $a$ which doesn't require the pigeonhole. So nice example, but not really practical I think. $\endgroup$
    – seancarmody
    Oct 18, 2020 at 7:25
12
$\begingroup$

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.

Improve this answer
$\endgroup$
12
$\begingroup$

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.$

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

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Should'nt your $n+1$ possible position be rather $n(n+1)/2$? This of course does not change the idea nor the statement. $\endgroup$
    – Benoît Kloeckner
    Apr 19, 2014 at 20:04
  • $\begingroup$ @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. $\endgroup$
    – Paul Draper
    Apr 20, 2014 at 3:26
  • $\begingroup$ 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? $\endgroup$
    – Brendan W. Sullivan
    Sep 19, 2014 at 14:25
9
$\begingroup$

Here is one application in introductory abstract algebra:

A finite integral domain is a field.

Improve this answer
$\endgroup$
5
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.