Take the 2-minute tour ×
Mathematics Educators Stack Exchange is a question and answer site for those involved in the field of teaching mathematics. It's 100% free, no registration required.

The Pigeonhole Principle (or Dirichlet's box principle) is a method introduced usually quite early in the mathematical curriculum. The examples where it is usually introduced are (in my humble experience) usually rather boring and not too deep.

It is well-known, however, that there are great and deep applications of it in research mathematics.

What applications of the pigeonhole principle would you consider in an "Introduction to proofs" course for university students? They should be non-trivial but accessible for undergraduate students, and an interchange between different mathematical fields is always welcome.

share|improve this question
2  
related reading: (#1) (#2) (#3) –  Alexander Gruber Apr 18 at 1:06
    
@AlexanderGruber: thank you. I should have included the first two in the question. –  András Bátkai Apr 18 at 6:56

6 Answers 6

  • If $\gcd(a,b)=1$, there exists a multiplicative inverse for $a$ modulo $b$. (Otherwise, look at the $b-1$ multiples of $a$, namely $a,2a,3a,\dots,(b-1)a$. They must fall into congruence classes that aren't 0 or 1, but there are only $b-2$ of those.)
  • $R(3,3)\leq 6$, and other Ramsey-style arguments
  • Give any domino tiling of a $6\times 6$ checkerboard, there exists a way to split the board along some row or column that does not disturb the tiling.
  • The Erdos-Szekeres result: Every sequence of length $ab+1$ contains a monotone increasing subsequence of length $a$ or a monotone decreasing subsequence of length $b$.
  • "Lossless data compression algorithms cannot guarantee compression for all input data sets. In other words, for any lossless data compression algorithm, there will be an input data set that does not get smaller when processed by the algorithm, and for any lossless data compression algorithm that makes at least one file smaller, there will be at least one file that it makes larger." (source and proof: Wikipedia)

If this is in an intro to proofs course, I also recommend stating the following version and having the students prove it. It's a good example of a contradiction argument: "Given any $n$ real numbers, at least one of them is as large as their average."

share|improve this answer
    
I'd prove it without contradicton (or pigeonhole principle): let $a_1$ be the largest of $a_1,\ldots,a_n$. Then the $a_1=a_1\cdot n/n\geq (a_1+\cdots+a_n)/n$. Actually, it's not obvious to me how you could even prove it using pigeonhole principle (though I see how you could prove it by contradiction, misguided as it seems to me). –  tomasz Apr 19 at 14:24

Dirichlet's theorem that an irrational number can be approximated to within $1/q^2$ for a sequence of rationals $p/q$ exemplifies this principle.

share|improve this answer

Application 1: Every rational number has a repeating decimal expansion.

Application 2: Each infinite decimal expansion has the property that there exists a $10^{100}$-length sequence of digits that is repeated infinitely often in the expansion.

Application 3: If $x$ is irrational, then at least two digits appear infinitely often in the decimal expansion of $x.$

share|improve this answer
    
I believe it is possible to construct non-repeating sequences... –  vonbrand Apr 18 at 3:05
2  
@vonbrand, all three statements are correct. –  Paul Draper Apr 18 at 22:28
4  
@tomasz, "infinitely often" seems to me to be exactly equivalent to "infinitely many times" –  Paul Draper Apr 19 at 16:14
2  
@tomasz "infinitely often" is entirely standard jargon. –  Gamma Function Apr 19 at 23:29
1  
@GammaFunction: be that as it may, I still consider it misleading, especially considering we're talking about education. –  tomasz Apr 20 at 1:28

Problem

Each point in the plane is colored one of $n$ colors. Prove that there exists a rectangle whose four vertices are the same color.

Both the problem and the solution are very simple, yet those unfamilar with the Pigeonhole Principle would likely be at a complete loss to solve it.


Solution

Consider a grid of points with $n+1$ rows and $n^{n(n+1)/2}+1$ columns.

  1. Since there are $n$ colors, by the Pigeonhole Principle, for each column there must be a pair of the $n+1$ grid points with the same color.
  2. Each column has $\frac{n(n+1)}2$ possible positions for this same-colored pair. Since there are $n$ colors, each column has one of $n^{n(n+1)/2}$ possible same-colored pairs. By the Pigeonhole principle, two of the $n^{n(n+1)/2}+1$ columns have the same pair, forming a rectangle.

This problem works even better when explained visually.

The USA Mathematical Talent Search asked this problem for the case $n=3$.

If you want, you can extend this to a hypercube in $k$ dimensions.

share|improve this answer
    
Should'nt your $n+1$ possible position be rather $n(n+1)/2$? This of course does not change the idea nor the statement. –  Benoît Kloeckner Apr 19 at 20:04
    
@BenoîtKloeckner, thank you. I fixed it. There are ways to reduce the number of grid points needed (assumptions without loss of generality), but this way is easiest to understand. –  Paul Draper Apr 20 at 3:26
    
I've been thinking about this a lot, and I'm confused by step 2. Shouldn't it be $\binom{n+1}{2}\cdot n$, i.e. multiplication not exponentiation? The idea is that you have $\binom{n+1}{2}$ "empty arrangements" of pairs of dots. Each one could be filled with one of the $n$ colors available (and then we don't even care what the colors of the other dots in the column are). Right? –  brendansullivan07 Sep 19 at 14:25

Here is one application in introductory abstract algebra:

A finite integral domain is a field.

share|improve this answer

Show that among any $n + 1$ numbers out of $1, \ldots, 2n$ there are two that are relatively prime, and there is one that divides the other.

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.