Xrhrft

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 $ntimes 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 $ntimes n$ square into four $frac{n}{2}timesfrac{n}{2}$ squares (pigeonholes). Consequently, at least two points (pigeons) are inside the same $frac{n}{2}timesfrac{n}{2}$ square.

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

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?

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.

Here are a few of my personal favourites:

1. The Erdos-Szekeres theorem is of course a classical example




2. Call $S = {a_1,...,a_{|S|}} subset {1,2,...,n}$ a Sidon set if all the pairwise sums $a_i+ a_j, i leq j$ are distinct. Then $|S| = O(n^{1/2})$

The proof is very simple. $S$ is equivalently a Sidon set if the ${|S| choose 2}$ pairwise differences are distinct. These can only take values from $1$ to $n-1$. So by the pigeonhole principle, ${|S| choose 2} leq n-1 implies |S| = O(n^{1/2})$. (The same proof can be replicated for the pairwise sums, but the differences give a better constant).

The beautiful thing about this proof is that the upper bound is very close to tight - there exist Sidon sets with size close to $n^{1/2}$.

3. Any prime $p$ not equal to $2$ or $5$ divides infinitely many of the integers, $11, 111, 1111, ...$
   

By the pigeonhole principle, infinitely many of them are in the same residue class mod $p$, and their pairwise differences are of the form $11...10..0$ Since $p$ is coprime to $10$, $p$ must divide the initial string of $1$'s.

There is a series of 3 articles on conception, identification and application of Pigeon-hole Principle See here.

The first article discusses about $k-to-1$ functions and next articles build upon it.

There is an interesting problem about finding minimum number of devotees in a temple, just by seeing the number of footwears outside the entrance.

Please note, I am the author of the blog.

How about the division problem?

let $A subseteq$ ${1,2,...,2n}, |A|=n+1$

show that there must be two elements $x, y$ $in A$ s.t $ xneq y $ and $x$ divides $y$.

Proof:

Any natural number can be denoted as: $N=2^k * m$, where $m$ is some odd number.

Since there are only $n$ odd numbers at most in $A$, there must be at least two numbers $a, b$ for which the greatest odd divisor $m$ is the same via PHP, hence one of them must divide the other.

Hope it helps!

There are great applications of pigeonhole principle (PHP) in some olympiad problems and some theorems, both in finite and infinite structures. I'll mention three of them here and some hints about solutions. Hope you'll find them useful:

1-Given five lattice points on the plane, we connect any two of them by drawing a line between them. so we draw 10 lines, between these points. Prove that there exist another lattice point on at least one of these lines.(By "lattice point" I mean points of the plane with integer coordinates)

(Hint: integer coordinates can be odd or even, and you are given 5 points! now look at the middle of lines.)

2- for any positive integer n, prove that there exist a multiple of n which its presentation in base 10 has only 0 and 1.

(Hint : consider a sequence 1,11,111,1111,... . look at this sequence modulo n and by PHP find the solution in the form of x-y where x and y are in this sequence.)

3- for any positive integer n, prove there exist a Fibonacci number divisible by $10^n$.

(Hint : again look at the sequence of fibonacci numbers modulo $10^n$ and try to prove that this sequence is a periodic sequence.)