## Interesting applications of the Pigeon-hole Principle

I'm a little late in realizing it, but today is Pigeon-hole Day. Festivities include thinking about awesome applications of the Pigeon-hole 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.

Brouwer's fixed point theorem can be proved with the Pigeon-hole 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!

-
Not an answer, but Terry Tao's blog post terrytao.wordpress.com/2007/05/23/… features the PHP. – Sonia Balagopalan Nov 5 2009 at 18:38
How strange. I had no idea about pigeon-hole day, but I came here to post a very similar topic (analogues of the pigeonhole principle). But I guess at any given moment, there are lots of people thinking about the pigeonhole principle, and there are only so many websites where such thoughts can reasonably be posted, so applying the...you know. – Darsh Ranjan Nov 5 2009 at 19:18
Excellent question. Has anyone asked for a list of applications of the inclusion-exclusion principle? The only sexy one that I know frequently appears in probability courses: the probability that a random permutation has no fixed points converges fairly fast to $1/e$ as the size of the set being permuted grows. – Michael Hardy Jun 13 2010 at 0:10

Given 5 point on a sphere, there must be a closed hemisphere that contains 4 of them.

-
I think this generalizes to given n+2 points on a n-dimensional hypersphere there is a closed hemisphere which contains n+1 of them. – Kristal Cantwell Nov 6 2009 at 17:33
@J. H. S.: yes, that's where I first saw it. – Anton Geraschenko Dec 16 2009 at 0:21
@J. H. S.: it's problem A2 on the 2002 Putnam. – Michael Lugo Dec 16 2009 at 0:29
@Anton: Do you know where this proposal first appeared? Wasn't it an A-something problem of a Putnam Examination? – J. H. S. May 7 2010 at 16:37

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.

-

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

-

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.

-
Yes, this was the first application, and Dirichlet then used it (together with an application of the infinite pigeonhole principle) to prove the existence of solutions of the Pell equation. See Supplement VIII of Dirichlet's Vorlesungen ueber Zahlentheorie. – John Stillwell Aug 19 2010 at 22:55

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

-
There are a lot of applications of the pigeonhole principle in Ramsey theory. I found a quote by Terence Tao: "Indeed one can view Ramsey thoery as the set of generalizations and repeated applications of the pigeonhole principle." This is from page 254 from the book Additive Combinatorics by Terence Tao and Van Vu. – Kristal Cantwell Nov 6 2009 at 17:41

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.

-

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

-
 Well, the actual author of this application is Siegel (1929). This lemma is known as Siegel's lemma in transcendental number theory. I am surprised it wasn't mentioned earlier. +1 – Wadim Zudilin Dec 3 2010 at 12:58 This lemma itself easily implies Roth's theorem, and so it does not belong to Siegel. But argument does, you are right (Roth's contribution concerns other ideas of the proof). – Fedor Petrov Dec 3 2010 at 13:29

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

-
The provided link is dead. :( – huitseeker Mar 3 2011 at 15:00
This has been fixed. – Richard Stanley Mar 5 2011 at 16:42
It seems to be broken again. – Andreas Blass Jan 26 2012 at 15:09
I found the (currently) correct url by googling on "rstan pigeon.pdf." – Barry Cipra Jan 26 2012 at 16: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.

-

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

-
This is a special case of the Erdos-Szekeres theorem: en.wikipedia.org/wiki/… . – Qiaochu Yuan Nov 5 2009 at 20:21

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.

-

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.

-

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.

-

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

-
A strengthening is this: there are certainly at least two bold people. – Boris Bukh Jun 2 2010 at 9:48
@Boris: this may be related to the slogan 'fortune favours the bald'. – Ketil Tveiten Dec 3 2010 at 14:07

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.

-

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

-
I believe you can find it in "Proof from the book", as for Brouwer theorem. – Gian Maria Dall'Ara Nov 7 2009 at 12:44

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.

-

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

-

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

-

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

-

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

-