Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
Two silly questions: where can I find the guidelines of what questions are supposed to be community wiki, and how do I make my question a community wiki question? I thought there was a button to click, but I can't see it in the edit page. –  Álvaro Lozano-Robledo Sep 7 '11 at 15:08
5  
Relevant MathOverflow question: Interesting applications of the Pigeon-hole Principle –  Rahul Sep 7 '11 at 15:50
31  
Also, "If you shoot $n$ pigeons with $m > n$ bullets, and never miss, there is at least one pigeon with more than one hole." –  Rahul Sep 7 '11 at 15:56
12  
@Rahul: This doesn't take into account the possibility of shooting through a previously made hole. Unless you count holes with multiplicity... :) –  anon Sep 7 '11 at 20:51
19  
@anon: Ah, but if the bullet goes clean through an existing hole, then you have not made contact with the pigeon. I count that as a miss. :) –  Rahul Sep 7 '11 at 20:54

20 Answers 20

up vote 29 down vote accepted

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

share|improve this answer
    
This is also my favorite! –  Byron Schmuland Sep 7 '11 at 15:42
    
I actually proved this in an answer I posted a month ago. It is my favorite application of the pigeonhole principle. –  robjohn Sep 7 '11 at 21:32
    
@robjohn Cool, I'll just link to your answer then. :) –  Srivatsan Sep 7 '11 at 21:39

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

share|improve this answer
1  
Given that the question asks for applications to prove theorems rather than for theorems without even a hint as to what the pigeons are, would you mind expanding on this answer? –  Peter Taylor Sep 7 '11 at 16:53
5  
I wanted to leave the fun part to the reader. =) –  Brendan Cordy Sep 7 '11 at 17:31
9  
If you really want one... Hint: Take any two of the points, on a sphere these two points determine a ______. –  Brendan Cordy Sep 7 '11 at 17:35
5  
@Louis: Pick any two of the points and draw a great circle through them around the sphere. Now this splits the other three into two possible hemispheres. The closed hemisphere of these two which has the greatest number of the givne points will have at least two of the remaining three as well as the original two on the equator, and we're done. (Or there will be degenerate cases of collinearity which can also be easily treated.) –  anon Sep 8 '11 at 4:22
4  
@Louis: There are three pigeons and two holes, so at least one hemisphere contains more than one point (apart from the original two). –  Rahul Sep 8 '11 at 6:12

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.

share|improve this answer
3  
This is really fascinating. If I was a teacher, I would start my lecture with: Does anybody know what 5 points on a sphere and and lossless data compression algorithm have in common? or similar... (and if I was a student listening to such introduction, I would just stare in disbelief, mesmerized...) –  VividD Jan 16 at 8:40

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.

share|improve this answer
    
Doesn't this require the generalized $\lceil n/m \rceil$ version? –  Random832 Sep 7 '11 at 18:07
    
@Random: Dear Random832, I guess so. Regards, –  Matt E Sep 7 '11 at 18:15

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.

share|improve this answer
    
Ah, Lajos Pósa... see here, and here –  t.b. Sep 7 '11 at 17:46
    
@Theo Great. I saw this remarkable proof a few years ago, but never knew the history. Thanks! (What a disappointment to find that exact page containing the proof is not included as a part of the preview. I can see the ones just before and after it. :-/) –  Srivatsan Sep 7 '11 at 17:50
    
Take this as an incentive to organize a copy of that book, then! I promise that you won't regret it :) –  t.b. Sep 7 '11 at 17:53

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

share|improve this answer

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

share|improve this answer
2  
Often expressed with people as vertices, and handshakes or friendship as edges. –  zyx Sep 7 '11 at 21:45
    
Of course, this assumes that the graph has no loops (or, equivalently, that no person shakes hands with him/herself). –  Ilmari Karonen Sep 8 '11 at 11:11

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

share|improve this answer
    
Source: mindyourdecisions.com/blog/2008/11/25/… –  George Sep 7 '11 at 18:02
    
For further reading: Ramsey's theorem –  Nate Eldredge Jan 30 at 15:01

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
1  
It's worth noting that the pigeonhole principle is actually stronger than the pumping lemma for regular languages: it's not very hard to construct formal languages which are pumpable, but which can be easily shown to be non-regular using the pigeonhole principle. For a nice example, see this question and Dave Radcliffe's answer to it. –  Ilmari Karonen Sep 8 '11 at 11:07
    
Did you mean: "it's not very hard to construct formal languages which are not pumpable, but which can be easily shown to be non-regular using the pigeonhole principle."? –  Giorgio Sep 8 '11 at 11:11
    
+1 Thanks for the feedback and the link. –  Giorgio Sep 8 '11 at 11:21
    
@Giorgio: There are non-regular languages that are always pumpable. Consider $L = \{a^i b^j c^k : i,j,k \geq 0 \wedge \ (i = 1 \Rightarrow j = k)\}$. $L$ is easily seen to be not regular, but it is easy to verify that every string in $L$ is pumpable. –  Brandon Carter Sep 8 '11 at 17:40
    
@Brandon Carter and Ilmari Karonen: yes, Ilmari 's formulation is correct. My mistake. Thanks. –  Giorgio Sep 8 '11 at 18:00

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

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

There are two people with the same number of hairs on their head in New York City.

share|improve this answer

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.