Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

Allow me to start with an example:

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!

share|improve this question
1  
Not an answer, but Terry Tao's blog post terrytao.wordpress.com/2007/05/23/… features the PHP. –  Sonia Balagopalan Nov 5 '09 at 18:38
53  
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 '09 at 19:18
1  
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 '10 at 0:10
add comment

21 Answers

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

share|improve this answer
2  
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 '09 at 17:33
    
@J. H. S.: yes, that's where I first saw it. –  Anton Geraschenko Dec 16 '09 at 0:21
1  
@J. H. S.: it's problem A2 on the 2002 Putnam. –  Michael Lugo Dec 16 '09 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 '10 at 16:37
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
1  
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 '10 at 22:55
add comment

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

share|improve this answer
3  
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 '09 at 17:41
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
    
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 '10 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 '10 at 13:29
add comment

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

share|improve this answer
    
The provided link is dead. :( –  huitseeker Mar 3 '11 at 15:00
    
This has been fixed. –  Richard Stanley Mar 5 '11 at 16:42
    
It seems to be broken again. –  Andreas Blass Jan 26 '12 at 15:09
4  
I found the (currently) correct url by googling on "rstan pigeon.pdf." –  Barry Cipra Jan 26 '12 at 16:11
add comment

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

share|improve this answer
add comment

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

share|improve this answer
3  
This is a special case of the Erdos-Szekeres theorem: en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem . –  Qiaochu Yuan Nov 5 '09 at 20:21
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
2  
A strengthening is this: there are certainly at least two bold people. –  Boris Bukh Jun 2 '10 at 9:48
4  
@Boris: this may be related to the slogan 'fortune favours the bald'. –  Ketil Tveiten Dec 3 '10 at 14:07
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
1  
I believe you can find it in "Proof from the book", as for Brouwer theorem. –  Gian Maria Dall'Ara Nov 7 '09 at 12:44
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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