What is your favorite application of the Pigeonhole Principle?

Question

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!

Answer 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.)

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

Answer 3

Given five points on a sphere, there is a closed hemisphere containing at least four of them.

Answer 4

This is a cute application of pigeonholing.

Find the size of the largest subset $A$ of $\{ 1,2 ,\ldots, 2n \}$ satisfying the following condition: if $a$ and $b$ are distinct elements of $A$, then $a$ does not divide $b$.

After some thought, one can come up with the example $A = \{ n+1, n+2, \ldots, 2n \}$ containing $n$ elements. But is this the best possible? Surprisingly, yes!

Towards a contradiction, assume $|A| \geqslant n+1$. Write each $a \in A$ as a product of an odd number (“the odd part of $a$”) and a power of $2$. Bin the elements $a \in A$ (“the pigeons”) in holes, such that two pigeons go into the same hole iff their odd parts are equal. Now the number of holes is $n$ (why?), and the number of pigeons is $\geqslant n+1$ by assumption. Thus, we are guaranteed to find a pair $a,b \in A$ whose odd parts are identical.

Can you see why we are now done?

Edit: Ok, this one is officially from THE BOOK! Thanks to t.b. for pointing it out.

Answer 5

One application that I like involves the case when $m$ is finite, but $n = \infty$. It will require a certain level of maturity for your students to appreciate this case of the principle, but (for me) the appeal is that it takes what looks like a very discrete math/combinatorical principle, and allows one to apply it to apparently quite different areas.

The best illustration I can think of is the proof of Bolzano--Weierstrass:

If $(x_n)$ is a sequence of real numbers lying in a bounded interval, than $(x_n)$ contains a Cauchy subsequence.

Proof: We will use the Pigeon Hole Principle (iteratively), with (in the notation of the question) $n = \infty$ and $m = 2$. Namely, divide the interval in half; since the sequence has infinitely many elements, infinitely many of them must lie in one of the two halves. Repeat this process, dividing that half in half and so on. Since there is at least one member (in fact infinitely many members) of the sequence lying in the chosen half at each stage of the construction, we can use them to pick out a subsequence, which is Cauchy by construction. QED

Another example (more manifestly combinatorial in its statement) is given by König's Lemma, which states that an infinite tree, each vertex of which has finite degree, must contain an infinitely long branch.

Answer 6

Every graph with two or more vertices has two vertices with the same degree.

Answer 7

This can be used to prove that the decimal form of a rational number either terminates or recurs (apply to the remainders).

Answer 8

A recent favorite of mine is the Erdős-Szekeres Theorem: Given a sequence of $n$ distinct numbers, if $n > rs$, there exists a monotonically decreasing subsequence of length at least $r + 1$ or a monotonically increasing subsequence of length at least $s + 1$.

A proof due to Seidenberg uses the pigeonhole principle. Essentially, for each element $a_i$ of the original sequence, plot the point $(a_i^+, a_i^-)$, where $a_i^+ =$ the length of the longest increasing subsequence ending at $a_i$, and $a_i^- =$ the length of the longest decreasing subsequence ending at $a_i$. There will be $n$ points, and if we proceed by contradiction to assume all decreasing subsequences have length $\leq r$ and all increasing subsequences have length $\leq s$, then that means all the points $(a_i^+, a_i^-)$ lie on positive integer lattice points in the $s \times r$ rectangle in the first quadrant. Since $n > rs$, at least one lattice point is filled by two such points, $(a_i^+, a_i^-) = (a_j^+, a_j^-)$, $j \neq i$. It's easy to show this is a contradiction.

Answer 9

Solvability of Pell's equation: If $D>0$ is a nonsquare, then there is a solution of $x^2-Dy^2=1$ other than $(\pm 1, 0)$. The proof is pigeonholing three times:

Proof: Since $\sqrt{D}$ is a real irrational, by Srivatsan's answer, there are infinitely many pairs $(p,q)$ such that $|q \sqrt{D} - p| \leq 1/q$. For such $p$ and $q$, we have $p < q \sqrt{D} + 1 < (q+1) \sqrt{D}$ so $$|p^2 - D q^2| < (1/q) (q+1) \sqrt{D} < 2 \sqrt{D}.$$ (Pigeonhole argument 1.)

So, as $(p,q)$ runs through the infinitely many solutions which Srivatsan obtains, the integers $p^2 - D q^2$ all lie in the interval $(-2 \sqrt{D}, 2 \sqrt{D})$. So, there must be some integer $m$ for which there are infinitely many solutions to $p^2 - D q^2 = m$. (Pigeonhole argument 2.) Moreover, since $D$ is not square, $m$ is not zero.

Now take our infinitely many solutions to $p^2 - D q^2$ and reduce them modulo $m$. So we can find different $(p_1, q_1)$ and $(p_2, q_2)$ with $p_1^2 - D q_1^2 = p_2^2 - D q_2^2 = m$, with $p_1 \equiv p_2 \bmod m$ and $q_1 \equiv q_2 \bmod m$. (Pigeonhole argument 3.)

We have $$(p_1+q_1 \sqrt{D})^{-1} (p_2 + q_2 \sqrt{D}) = \frac{(p_1 p_2 - D q_1 q_2) + (p_1 q_2 - p_2 q_1) \sqrt{D}}{p_1^2 - D q_1^2} = P + Q \sqrt{D} \quad (1)$$ where $$P = \frac{p_1 p_2 - D q_1 q_2}{m} \quad Q = \frac{p_1 q_2 - p_2 q_1}{m}.$$ Since $p_1 \equiv p_2 \bmod m$, $q_1 \equiv q_2 \bmod m$ and $p_1^2 \equiv D q_1^2 \bmod m$, we see that $P$ and $Q$ are integers.

Taking the norm of both sides of $(1)$, we get $$P^2 - D Q^2 = \frac{p_2^2 - D q_2^2}{p_1^2 - D q_1^2} = \frac{m}{m} = 1.$$

Answer 10

In a group of six people, there will always be three people that are mutual friends or mutual strangers. (Assume that “friend” is symmetric-if x is a friend of y, then y is a friend of x.)

The problem can be thought of geometrically. Imagine the six people as points and let an edge between points indicate friendship. No matter how the graph is drawn, we want to show there is a set of three points that are all connected or a set of three points that has no connecting edges.

Consider any single point. There are five other points it could possibly connect to. By the pigeonhole principle, the point is either connected to at least three other points or not connected to at least three other points.

Case 1: the point is connected to (at least) three other points If any of these points are connected to each other, then we have found a triangle of three mutual friends. (These two points are connected, plus they are both connected to the original point).

Otherwise, that means none of these three points are connected and hence they are mutual strangers. This would be a set of three points without any edges.

Case 2: the point is not connected to (at least) three other points If any of these points are not connected to each other, then we have found a triangle of three mutual strangers. (These two points are not connected, plus they are both not connected to the original point).

Otherwise, that means all of these three points are connected and hence they are mutual friends. This would be a set of three points with all connecting edges.

Answer 11

There are at least 2 people on earth right now with exactly same number of hairs on their bodies.

Answer 12

An example almost isomorphic to the proof of Bolzano-Weierstrass is the proof of the following infinite Ramsey theorem: if the edges of the countably infinite complete graph $K_\omega$ are colored black or white, then $K_\omega$ contains an infinite monochromatic complete subgraph.

Step 1. Pick a vertex $v_0$ of $K_\omega$. By the infinite pigeonhole principle, infinitely many edges out of $v_1$ have the same color. Let $V_1$ be the set of vertices to which these edges lead, and let $v_1$ be a member of $V_1$.

Step 2. By the infinite pigeonhole principle again, infinitely many edges out of $v_1$ to other edges in $V_1$ have the same color. Let $V_2$ be the set of vertices to which these edges lead, and let $v_2$ be a member of $V_2$.

Repeating this process, we obtain vertices $v_1,v_2,v_3,\ldots$ such that the edges from $v_n$ to $v_{n+1},v_{n+2},\ldots$ are all of the same color. The color may depend on $n$ but, by the infinite pigeonhole principle again, the same color occurs infinitely often.

Therefore, we can choose an infinite subsequence $w_1,w_2,w_3,\ldots$ of $v_1,v_2,v_3,\ldots$ such that

color of edges from $w_1$ to $w_2,w_3,\ldots$ =

color of edges from $w_2$ to $w_3,w_4,\ldots$ =

color of edges from $w_3$ to $w_4,w_5,\ldots$

and so on.

Hence the graph with vertices $w_1,w_2,w_3,\ldots$ is the required monochromatic graph.

Answer 13

A useful and well-known application is the proof of pumping lemmas in formal language theory, e.g. for regular languages.

For regular languages the argument goes as follows. Every regular language $L$ can be recognized by some deterministic finite automaton $A$ with $m$ states. If we scan a string $w$ that is long enough ($|w| = n > m$), the automaton will visit at least one state $q$ at least twice.

This means that $w$ can be decomposed into three segments $xvy$, with $|v| > 0$, such that the automaton is in state $q$ after scanning $x$ and after scanning $xv$. As a consequence, we can pump the string to $w^{\prime} = xv^ky$ for an arbitrary $k\geq 0$, and we have $w^{\prime}\in L$ iff $w\in L$.

This property can be used e.g. to show that certain languages are not regular. For example, the language $\{ a^k b^k \mid k\geq 0 \}$ is not regular.

Answer 14

This is by far my favorite undergraduate application of the pigeonhole principle, I'll present it as exercise.

Let $x_1, x_2, ..., x_7 \in \mathbb{R}$, then there are distinct positive integers $i, j \leq 7$ such that $$ 0 \leq \frac{x_i - x_j}{1 + x_i x_j} \leq \frac{1}{\sqrt{3}}. $$ Hint: write every $x_i = \tan (\theta_i)$.

Answer 15

Here are a couple of finite-and-infinite versions:

If infinitely many objects are put into $m < \infty$ places, then at least one of the $m$ places receives infinitely many objects. If into each of infinitely many places at least one of $n < \infty$ objects is placed (repetition of objects allowed), then at least one object will be placed infinitely many times.

Here's a neat application of the second version above.

Every infinite decimal expansion has the following property. For each positive integer $n$, there exists a sequence of $n$ digits that appears infinitely often in the decimal expansion. I will show this for $n=3$ using an argument that requires only trivial changes for the general case. There are $10^{3}$ many 3-digit sequences and infinitely many locations in the decimal expansion where a 3-digit sequence can appear. Therefore, at least one of the $10^{3}$ many 3-digit sequences must make infinitely many appearances.

Answer 16

A well-known exercise: Suppose $G$ is a finite set which satisfies all the group axioms except the existence of inverse. Suppose it has instead the property that for all $a, b, c$, we have that $ac = bc$ implies that $a =b$. Then $G$ is in fact a group. Seen by the observation that for an arbitrary $x$, the sequence $x, x^2, x^3, \ldots$, must repeat somewhere.

Answer 17

One of my favorite pigeonhole proofs is a little-known "fewunit" ring-theoretic generalization of Euclid's classic proof that there are infinitely many primes. Namely, in this answer, generalizing Euclid's classic argument, is a simple proof that an infinite ring has infinitely many maximal (so prime) ideals if it has fewer units than elements (i.e. smaller cardinality). The key idea is that Euclid's construction of a new prime generalizes from elements to ideals, i.e. given some maximal ideals $\rm P_1,\ldots,P_k$ then a simple pigeonhole argument employing $\rm CRT$ implies that $\rm 1 + P_1\cdots P_k$ contains a nonunit, which lies in some maximal ideal $\rm P$ which, by construction, is comaximal (so distinct) from the prior max ideals $\rm P_i$.

Answer 18

This is a complement to Srivatsan Narayanan's answer above on rational approximations to irrationals.

Peter Markstein, in his book IA-64 and Elementary Functions, Prentice-Hall, 2000, has this very nice Exclusion Theorem in Section 6.3, pages 91 and 92. This theorem was used in the design of the code for the elementary functions on Intel's IA-64 processor, which gives correctly rounded results. I reproduce Section 6.3 verbatim:

---

When seeking the root of a polynomial with integer coefficients, it is possible to determine the number of significant digits in an approximation which will guarantee correct rounding to a given precision, when the approximation is rational (floating point numbers are always rational). The exclusion theorem exemplifies the analysis carried out by Dirichlet [10] and Liouville in their early studies of transcendental numbers.

Theorem (the Exclusion Theorem.)

Let $\xi$ be a root of the polynomial $p_n(x) = \sum_{i=0}^n c_ix^i$, and let $a/b$ be an approximation sufficiently close to $\xi$, where $a$, $b$, and $c_i$ are integers. Then $|\xi-a/b| \ge M(\xi)/b^n$, where $M(\xi)$ is a constant which depends on $\xi$ and $p_n$.

Proof. First, observe that $$ \left|p_n\left(\frac{a}{b}\right)\right| = \left|\sum_{i=0}^n\frac{c_ia^ib^{n-i}}{b^n}\right| \ge \frac{1}{b^n} $$ when $a/b$ is not exactly $\xi$, because all quantities in the numerator of the summation are integers. Consider the interval $(\xi-1,\xi + 1)$. If $a/b \in (\xi-1,\xi + 1)$, and $a/b$ is closer to $\xi$ than any other root of $p_n$, then from the mean value theorem, $$ p_n\left(\frac{a}{b}\right) - p_n(\xi) = \left(\frac{a}{b} - \xi\right)p_{n}'(w),\, w\in \left(\frac{a}{b},\xi\right) $$ Since $p_n(\xi) = 0$, $$ \left|\frac{a}{b} - \xi\right| \ge \left|\frac{1}{b^n p_{n}'(w)}\right| $$ $p_{n}'(w)$ can be replaced by the maximum value it takes on in the interval $(\xi-1,\xi + 1)$, giving $|a/b - \xi| \ge M(\xi)/b^n$. $\blacksquare$

Using the exclusion theorem, an interval around $\xi$ can be determined within which no rational number having $b$ as its denominator can exist. If a computation is to be rounded to $p$ bits, then taking $b=2^{p+1}$ will establish an interval about $\xi$ in which no number halfway between two numbers of precision $p$ can lie. Computing an approximation to $\xi$ which lies in the excluded interval guarantees that rounding to $p$ precision is correct.

Real numbers which are the roots of polynomials with integer coefficients are called algebraic numbers; all other real numbers are transcendental. The algebraic numbers are distinguished by the exclusion theorem, which establishes for a given integer $b$, an interval within which no rational approximation with a denominator $b$ can exist. For transcendental numbers $\tau$, approximations generally can be found which are arbitrarily close to $\tau$. The lack of a similar exclusion theorem for approximations to transcendental numbers is the cause of difficulty in rounding transcendental functions correctly with modest effort.

[End of Section 6.3, verbatim]

See also Ng -- Argument Reduction for Huge Arguments

Answer 19

In every group of six people there will be atleast three mutual acquantances or three mutual strangers.

Though this can be included in the answers mentioning Ramsey Theory, it is quite a favorite of mine. See this question.

Answer 20

Van der Waerden's theorem:

Fix a coloring of the natural numbers with two colors. Then for any given positive integer $n$ there is a monochromatic arithmetic progression of length $n$.

For a proof one can refer to Ramsey Theory by Graham, Rothschild, and Spencer.

Answer 21

In a finite semigroup $S$, every element has an idempotent power, i.e. for every $s \in S$ there exists some $k$ such that $s^k$ is idempotent, i.e. $(s^{k})^2 = s^k$. For the proof consider the sequence $s, s^2, s^3, \ldots$ which has to repeat somewhere, let $s^n = s^{n+p}$, then inductively $s^{(n + u) + vp} = s^{n + u}$ for all $u,v \in \mathbb N_0$, so in particular for $k = np$ we have $s^{2k} = s^{np + np} = s^{np} = s^k$.

This result is used in the algebraic theory of automata in computer science.

Answer 22

Let $p=6k-1$ be a prime.

Theorem: Modulo $p$, if $a^3=b^3$ then $a=b$.

Proof. Suppose $x\ne 0$. Then, by Fermat's little theorem, $x^{p-1}=1$, so $x=(x^{p-1})^2x=x^{2p-1}=x^{12k-3}=(x^{4k-1})^3$ is a cubic residue mod $p$. 0 is a cubic residue, too, so every residue is a cubic residue. By the pigeonhole principle, every residue is a cubic residue exactly once. Thus $a^3=b^3$ implies $a=b$.

Here the $x^3$ mod $p$ are the pigeons and the $x$ mod $p$ are the holes.

Answer 23

Things like: Pigeon hole principle with sum of 5 integers but applied to integer polynomials. This shows, for example that any integer polynomial ( with integer inputs to guarantee integer output) that has 5x+17 terms, can be reduced to a polynomial with just 12 or fewer terms, mod 5. Stick that somewhere polynomial remainder theorem .