6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Nice question +1 $\endgroup$ – Maria Mazur Apr 5 at 16:11
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

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

$\endgroup$
2
$\begingroup$

Here's some relatively challenging problems, where the 'pigeonhole part' isn't always immediately obvious.

Show that for any $x\in\mathbb{Z}^+ $, there exists a Fibonacci Number that is divisible by $x$. (It may be helpful to consider a few cases first, such as $10^{10}$, then to generalize the proof. This is also a generalisation of Sim000's 3rd problem.)

There are $n$ distinct positive integers $a_1,a_2,\dots, a_n$ For any seqeuence $b_1,b_2,\dots, b_n$, where $b_i\in \{-1,0,1\}$ for $1\leq i\leq n$ and the terms are not all zero, $n^3\nmid a_1b_1+a_2b_2+\dots + a_nb_n$. Find the maximum possible value of $n$.

A student, who has $11$ weeks to prepare for an upcoming Olympiad, decides to sit one practice exam every day. However, due to time constraints, the student cannot sit more than $12$ practice exams in any $7$-day period. Prove that there are consecutive days during which the student sits exactly 21 practice exams.

The prime factorisations of $n+1$ positive integers $x_1,x_2,\dots, x_{n+1}$ only involve $n$ primes $p_1,\dots, p_n$. Prove that there exists a nonempty subset of $\{x_1,\dots, x_{n+1}\}$ whose elements multiply to a perfect square.

Suppose real numbers $x_1,\dots, x_n$ satisfy $\sum x_i^2=1$. Prove for integers $k\geq 2$, there exists integers $y_1,\dots, y_n$ not all zero such that $|y_i|\leq k-1$ for $1\leq i\leq n$ and $$\Biggl |\sum x_iy_i\Biggl| \leq \frac{\sqrt{n}(k-1)}{k^n-1}$$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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 $ x\neq 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!

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

The following problem is stated in Proofs from THE BOOK:

Paul Erdős attributes the following nice application of the pigeon-hole principle to Andre Vázsonyi and Marta Sved:

  • Claim. Suppose we are given $n$ integers $a_1,\ldots, a_n$, which need not be distinct. Then there is always a set of consecutive numbers $a_{k+1},a_{k+2},\ldots,a_l$ whose sum $\sum_{i=k+1}^la_i$ is a multiple of $n$.
$\endgroup$
  • 1
    $\begingroup$ This book is a great source of mathemtical beuty and attraction !! There are some great discussions in this book (in many branchs of mathematics) that I think can attract anyone! $\endgroup$ – Sim000 Mar 22 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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