53
$\begingroup$

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!

$\endgroup$
3
  • 1
    $\begingroup$ Not an answer, but Terry Tao's blog post terrytao.wordpress.com/2007/05/23/… features the PHP. $\endgroup$ Nov 5, 2009 at 18:38
  • 64
    $\begingroup$ 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. $\endgroup$ Nov 5, 2009 at 19:18
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 13, 2010 at 0:10

21 Answers 21

32
$\begingroup$

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.

$\endgroup$
1
  • 4
    $\begingroup$ 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. $\endgroup$ Nov 6, 2009 at 17:33
25
$\begingroup$

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.

$\endgroup$
1
20
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 19, 2010 at 22:55
18
$\begingroup$

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

$\endgroup$
15
$\begingroup$

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

$\endgroup$
1
  • 6
    $\begingroup$ 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. $\endgroup$ Nov 6, 2009 at 17:41
11
$\begingroup$

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

$\endgroup$
2
  • 5
    $\begingroup$ This is a special case of the Erdos-Szekeres theorem: en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem . $\endgroup$ Nov 5, 2009 at 20:21
  • $\begingroup$ Alternative one-line proof: Apply Robinson-Schendsted insertion on the sequence. The resulting tableau cannot (by the pigeon-hole principle) be contained in an nxn-square, so the first row, or first column must have length n+1 at least. But properties of RSK says these are the lengths of longest increasing/decreasing subsequences. $\endgroup$ May 16, 2019 at 14:16
10
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Could you please indicate a reference? It really interests me. Thank you very much. $\endgroup$
    – matgaio
    Mar 15, 2017 at 19:11
  • $\begingroup$ This still interests me! =) $\endgroup$
    – matgaio
    Jun 29, 2020 at 7:02
  • 1
    $\begingroup$ @matgaio Sorry I didn’t notice for so long! Check out section III.H of the book Metric spaces of non-positive curvature by Bridson and Haefliger. $\endgroup$
    – HJRW
    Jun 29, 2020 at 7:31
10
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$ Dec 3, 2010 at 12:58
  • $\begingroup$ 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). $\endgroup$ Dec 3, 2010 at 13:29
9
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ The provided link is dead. :( $\endgroup$
    – Francois G
    Mar 3, 2011 at 15:00
  • $\begingroup$ This has been fixed. $\endgroup$ Mar 5, 2011 at 16:42
  • 6
    $\begingroup$ I found the (currently) correct url by googling on "rstan pigeon.pdf." $\endgroup$ Jan 26, 2012 at 16:11
  • 1
    $\begingroup$ I have reposted this at math.mit.edu/~rstan/pigeon.pdf. $\endgroup$ May 12, 2015 at 1:37
  • 2
    $\begingroup$ The file can be found in Internet Archive. $\endgroup$ Jul 22, 2017 at 6:39
8
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ A strengthening is this: there are certainly at least two bold people. $\endgroup$
    – Boris Bukh
    Jun 2, 2010 at 9:48
  • 4
    $\begingroup$ @Boris: this may be related to the slogan 'fortune favours the bald'. $\endgroup$ Dec 3, 2010 at 14:07
5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ I believe you can find it in "Proof from the book", as for Brouwer theorem. $\endgroup$ Nov 7, 2009 at 12:44
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ I guess it is the Pigeonhole Principle, but it seems that the question "What happens to the different strings 0 and 1?" is just as convincing whether or not we mention that principle. $\endgroup$
    – LSpice
    May 15, 2019 at 18:59
0
$\begingroup$

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

$\endgroup$

Your Answer

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

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