[Math] Examples of the Pigeonhole Principle

big-listcontest-mathpigeonhole-principlesoft-question

As most of you might know, the Pigeonhole Principle basically states that

If $n$ items are put into $m$ containers, with $n>m$, then at least one container must contain more than one item

It always surprises me how this trivial – and at the same time powerful – idea might be the key in order to solve extremely complicated math olympiad-problems…

Quick and beautiful solutions are characteristic of pigeonhole problems, which are often a three-part process

  • Recognize that the problem requires the Pigeonhole Principle
  • Figure out what the pigeons and what the pigeonholes might be
  • After applying the pigeonhole principle, there is often more work to be done

I'll illustrate this with an example I've always liked…

(Example-)Problem: Given a $n\times n$ square, prove that if $5$ points are placed randomly inside the square, then two of them are at most $\frac{n}{\sqrt2}$ units apart.

Step 1: This problem can be solved with the Pigeonhole Principle

Step 2: We divide the $n\times n$ square into four $\frac{n}{2}\times\frac{n}{2}$ squares (pigeonholes). Consequently, at least two points (pigeons) are inside the same $\frac{n}{2}\times\frac{n}{2}$ square.

Step 3: The maximal distance between two points in an $\frac{n}{2}\times\frac{n}{2}$ square is the diagonal, which has the length $\frac{n}{\sqrt2}\qquad\square$

Another problem which can be solved with the Pigeonprinciple is the following:

IMO $1972/1$

Prove that from a set of ten distinct two-digit numbers (in the decimal system), it is possible to select two disjoint subsets whose members have the same sum.

At this point, you might have noticed how useful the Pigeonhole Principle can be, if you know how to recognize and use it.

Question: I would like to work on this amazing principle with my students for a week and was, therefore, gathering problems related to the Pigeonhole Principle with beautiful solutions.
Could you suggest some more?

Best Answer

Here's some list of problems that I know (I don't know references at all)

  • Choose 51 numbers from $\{1, 2, 3, \dots, 100\}$, then at least two of them are coprime.

  • Choose 51 numbers from $\{1, 2, 3, \dots, 100\}$, then one of them divides the other one.

  • For any irrational $x$, there exists infinitely many integers $p, q$ such that $|x-p/q| < 1/q^{2}$. (Dirichlet's approximation theorem)

You can find other examples here.

Related Question