Learn more about the Pigeonhole Principle and other powerful techniques for combinatorics problems in our Intermediate Counting & Probability textbook by USA Math Olympiad winner (and MIT PhD) David Patrick.

# Pigeonhole Principle

The Pigeonhole Principle (also known as the Dirichlet box principle, Dirichlet principle or box principle) states that if $n + 1$ or more pigeons are placed in $n$ holes, then one hole must contain two or more pigeons. Another definition could be phrased as among any $n$ integers, there are two with the same modulo- $n-1$ residue.

Although this theorem seems obvious, many challenging olympiad problems can be solved by applying the Pigeonhole Principle. Often, a clever choice of box is necessary.

The extended version of the Pigeonhole Principle states that if $k$ objects are placed in $n$ boxes then at least one box must hold at least $\left\lceil \frac{k}{n} \right\rceil$ objects. Here $\lceil \cdot \rceil$ denotes the ceiling function.

## Examples

### Introductory Problems

1. If a Martian has an infinite number of red, blue, yellow, and black socks in a drawer, how many socks must the Martian pull out of the drawer to guarantee he has a pair? (Solution)
2. Suppose $S$ is a set of $n + 1$ integers. Prove that there exist distinct $a, b \in S$ such that $a - b$ is a multiple of $n$. (Solution)

### Intermediate Problems

1. Show that in any group of $n$ people, there are two who have an identical number of friends within the group. (Solution)
(Mathematical Circles)
2. Six distinct positive integers are randomly chosen between 1 and 2006, inclusive. What is the probability that some pair of these integers has a difference that is a multiple of 5? (Solution) $\mathrm{(A) \ } \frac{1}{2}\qquad\mathrm{(B) \ } \frac{3}{5}\qquad\mathrm{(C) \ } \frac{2}{3}\qquad\mathrm{(D) \ } \frac{4}{5}\qquad\mathrm{(E) \ } 1\qquad$
3. Show that for any irrational ${x\in\mathbb R}$ and positive integer ${n}$, there exists a rational number ${\frac pq}$ with $1\le q\le n$ such that $\left|x-\frac pq\right|<\frac 1{nq}.$ (Solution)
(the classical Rational Approximation Theorem)

1. Seven line segments, with lengths no greater than 10 inches, and no shorter than 1 inch, are given. Show that one can choose three of them to represent the sides of a triangle. (Solution)
2. Prove that having 100 whole numbers, one can choose 15 of them so that the difference of any two is divisible by 7. (Solution)
6. There are 51 senators in a senate. The senate needs to be divided into $n$ committees such that each senator is on exactly one committee. Each senator hates exactly three other senators. (If senator A hates senator B, then senator B does 'not' necessarily hate senator A.) Find the smallest $n$ such that it is always possible to arrange the committees so that no senator hates another senator on his or her committee. (Solution)