Pigeonhole Principle is the habit of forcing a collision or concentration when more objects than containers are present. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.
$$\text{If } n \text{ objects go into } k \text{ boxes, some box holds at least } \left\lceil \tfrac{n}{k} \right\rceil \text{ objects.}$$
If you put more objects than boxes, at least one box must contain more than one object.
Why It Works
1
Suppose every box held at most $\lceil n/k \rceil - 1$ objects.
2
Then the total would be at most $k\left(\lceil n/k \rceil - 1\right) < k \cdot \tfrac{n}{k} = n$, since $\lceil n/k \rceil - 1 < n/k$.
3
That contradicts having exactly $n$ objects, so some box must hold at least $\lceil n/k \rceil$.
4
The basic version ($n > k$ forces a box with $\ge 2$) is the case worth memorizing; the ceiling form is the quantitative upgrade.
Worked Examples
Example 1
Show that in any group of $13$ people, at least two were born in the same month.
1
Treat the $13$ people as objects and the $12$ months as boxes.
2
Since $13 > 12$, the people cannot all fall in distinct months.
3
By pigeonhole, at least $\lceil 13/12 \rceil = 2$ people share a box (month).
Answer:
Yes — with $13$ people and only $12$ months, two must share a birth month.
Warm-up
A drawer holds socks in $3$ colors, mixed together in the dark. How many socks must you pull out to guarantee a matching pair?
1
Treat the $3$ colors as boxes. To force a box with $2$ socks (a matching pair), you need more socks than colors.
2
With $3$ socks you could get one of each color — no pair guaranteed.
3
With $4$ socks, since $4 > 3$, pigeonhole forces some color to appear at least $\lceil 4/3 \rceil = 2$ times.
Answer:
$4$
Contest level
Show that among any $5$ integers, some pair has a difference divisible by $4$.
1
Classify each integer by its remainder modulo $4$; the possible remainders $\{0, 1, 2, 3\}$ are $4$ boxes.
2
We have $5$ integers (objects) and only $4$ remainder classes (boxes), and $5 > 4$.
3
By pigeonhole two of the integers share a remainder, say $a \equiv b \pmod 4$.
4
Then $4 \mid (a - b)$, giving the required pair.
Answer:
Proven — $5$ integers, $4$ residue classes, so two coincide and their difference is divisible by $4$.
Olympiad / Challenge
Choose any $51$ numbers from $\{1, 2, \ldots, 100\}$. Prove that two of the chosen numbers are consecutive (differ by exactly $1$).
1
Partition $\{1, \ldots, 100\}$ into $50$ consecutive pairs: $\{1,2\}, \{3,4\}, \ldots, \{99,100\}$ — these $50$ pairs are the boxes.
2
We pick $51$ numbers and drop them into these $50$ boxes; since $51 > 50$, some box receives at least $\lceil 51/50 \rceil = 2$ numbers.
3
A box is a pair of consecutive integers, so the two numbers landing in it differ by exactly $1$.
4
Hence any $51$-element selection contains two consecutive numbers. (The bound is sharp: the $50$ odd numbers $\{1,3,\ldots,99\}$ have no consecutive pair.)
Answer:
Proven — $50$ consecutive-pair boxes, $51$ choices, so one box gets both its elements.
Going Deeper
The quantitative form says $n$ objects in $k$ boxes force some box with $\ge \lceil n/k \rceil$. The deeper skill is engineering the boxes: residue classes mod $m$, consecutive blocks, or sub-intervals. A celebrated example is that any $n+1$ numbers from $\{1,\ldots,2n\}$ contain a pair where one divides the other (box each number by its largest odd divisor).
It dominates existence and 'guarantee' problems on olympiads — proving two people have the same number of acquaintances, that some partial sums coincide mod $n$, or that points in a region must be close. Whenever a problem says 'show that there must exist,' pigeonhole is the first tool to try.
Pitfall: pigeonhole proves existence, never construction or location — it tells you two objects collide but not which two. The other trap is mis-sizing the boxes: you must have strictly more objects than boxes (or use the ceiling form correctly). Off-by-one errors in 'how many to guarantee' are rampant: $k$ boxes need $k+1$ objects to force a repeat, not $k$.
Spot the Signal
Look for problems where the key step is forcing a collision or concentration when more objects than containers are present.
You can describe the hard part as forcing a collision or concentration when more objects than containers are present, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.
Learn the Move
Start by identify the counting object that calls for pigeonhole principle, then rewrite the givens around it.
Name the relation that makes Pigeonhole Principle legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.
Avoid These Traps
Do not use Pigeonhole Principle just because the surface looks familiar; verify the required condition first.
Applying Pigeonhole Principle because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.
MathGrit Coach Note
Let pigeonhole principle reveal the counting structure; then compute only what remains.
Try it on:
Practice a contest problem where the key step is forcing a collision or concentration when more objects than containers are present.