Interesting applications of the pigeonhole principle

Question

I'm a little late in realizing it, but today is Pigeonhole Day. Festivities include thinking about awesome applications of the Pigeonhole Principle. So let's come up with some. As always with these kinds of questions, please only post one answer per post so that it's easy for people to vote on them.

Allow me to start with an example:

Brouwer's fixed point theorem can be proved with the Pigeonhole Principle via Sperner's lemma. There's a proof in Proofs from The Book (unfortunately, the google books preview is missing page 148)

By the way, if you happen to be in Evans at Berkeley today, come play musical chairs at tea!

Answer 1

Given 5 point on a sphere, there must be a closed hemisphere that contains 4 of them. See Problem A-2 of the 2002 Putnam Examination.

Answer 2

Kronecker's theorem asserts that if $\lambda$ is irrational then the orbit of $n\lambda$ for $n=1,2,3,\ldots$ is dense in $S^1$ $\simeq$ $\mathbb{R}/\mathbb{Z}$. A proof uses the Pigeon-hole Principle. It relies on the fact that if you divide $S^1$ into $k$ equal (but very small) segments you must hit one of these segments twice, by the Pigeon-hole Principle.

Answer 3

If I'm not mistaken, the original application of the Pigeonhole Principle - the reason we call it Dirichlet's Pigeonhole Principle - was to Dirichlet's Theorem on Diophantine Approximation, viz., if $\alpha$ is a real irrational then there are infinitely many rationals $p/q$ such that $|\alpha-(p/q)|<1/q^2$. An oldie, but still a goodie.

Answer 4

The pumping lemma, which gives a pretty good test to show that some languages are not regular. (There are also more general pumping lemmas that use pigeonhole for their proofs, but I don't know them.)

Answer 5

If we're allowed repeated application of the pigeonhole principle, the infinite version of Ramsey's theorem (finite colourings).

Answer 6

A simple application is the following:

Every sequence of $n^2 +1$ distinct real numbers contains a subsequence of length $n +1$ that is either strictly increasing or strictly decreasing.

(Other simple consequences can be found here.)

Answer 7

The easiest proof I know of the Morse Property for word-hyperbolic groups (which says that quasigeodesics are uniformly close to geodesics) uses the pigeon-hole principle several times.

Answer 8

It looks like the following very important example is not still mentioned here.

Pigeonhole principle plays a crucial role in K. F. Roth's proof that for any $\kappa>2$ and any algebraic irrational real number $\alpha$ inequality $|\alpha-p/q| < q^{-\kappa}$ has only finitely many solutions for rational fractions $p/q$.

(Lemma 9 in: K. F. Roth, Rational approximation to algebraic numbers, Mathematika 2 (1955), 1-20).

Answer 9

A couple that I've always found cute even though (or because?) they're completely elementary:

1) Every rational number has an eventually repeating decimal expansion.
2) Every element of a finite group has an order.

Answer 10

Some problems whose solutions involve the pigeonhole principle are at http://math.mit.edu/~rstan/a34/pigeon.pdf

Answer 11

I always find this fun to think about: in any group of six people there are either three mutual friends or three mutual strangers.

Answer 12

For most cardinals $\kappa \leq \lambda$, it must happen that the infinite symmetric group $S_\kappa$ satisfies exactly the same first order theory as $S_\lambda$. That is, the groups are elementarily equivalent. This is just because there are only continuum many theories in a countable language, but more cardinals than that.

See Elementary equivalence of infinitary symmetric groups.

Answer 13

The compactness of the Cantor space.

This follows directly from Konig's lemma which itself is a direct consequence of the infinite version of the pigeonhole principle.

Answer 14

I remember hearing as an undergrad the "proof" that there are two human beings on the earth with the same number of hairs on their heads. This is done by a few estimations and then applying the pigeonhole principle.

A number of examples including a version of this one can be found here: http://www.cut-the-knot.org/do_you_know/pigeon.shtml

Answer 15

I think, this proof of Sergei Ivanov that any $m$-fold cover of Riemann manifold has diameter at most $m$ times greater then the base is spectacular application of the PHP.

Answer 16

I think the solutions of these questions are very interesting (by using pigeon-hole principle), first question is easy, but second question is more advanced:

1) For any integer $n$, There are infinite integer numbers with digits only $0$ and $1$ where they are divisible to $n$.

2) For any sequence $s=a_1a_2\cdots a_n$, there is at least one $k$, such that $2^k$ begin with $s$.

Answer 17

Thue's Lemma, which plays a key role in one proof Fermat's theorem on primes that can be written as the sum of two squares, is based on the pigeonhole principle. (The wikipedia does not mention this and I could not find a nice web page on Thue's Lemma to cite here, so I can only suggest LeVeque's Fundamentals of Number Theory.)

Answer 18

Miklos Laczkovich's book Conjecture and Proof has some interesting theorems with pigeonhole proofs, such as the classification of primes that are sums of two squares, and bounds on Sidon sequences.

Answer 19

M. A. Lukomskaya's proof of van der Waerden's theorem on arithmetic progressions is a remarkable application of the Schubfachprinzip and induction.

Answer 20

The impossibility of a lossless compression scheme for binary strings that reduces the size of every input follows easily from the pigeon hole principle.

Answer 21

This, of course, requires some heavier theorems in Cech cohomology: If $X$ is a separated scheme that's covered by $d$ affine opens and $\mathcal{F}$ is a quasi-coherent sheaf on $X$, then $H^p(X,\mathcal{F}) = 0$ for all $p \geq d$. As a corollary: if $X$ is a quasi-projective scheme over a Noetherian ring $A$, and $\mathcal{F}$ is a quasi-coherent sheaf, then $H^p(X,\mathcal{F}) = 0$ for all $p > d$ where $d = \dim(X)$ (note that $X$ is covered by $d+1$ affines).