Here is a fact so obvious it sounds like a joke: if you put
13 pigeons into 12 holes, some hole holds at
least two pigeons. You cannot avoid it — there simply are not enough holes to give everyone
their own. That childish observation, dressed up, is the pigeonhole principle, and it
proves things that look genuinely surprising. Its power is that it guarantees a collision
without telling you where — a pure existence weapon.
-
Basic form. If n objects are placed into
m boxes and n > m, then some box contains at
least two objects.
-
Generalised form. If n objects go into
m boxes, some box contains at least
\left\lceil \dfrac{n}{m} \right\rceil objects. (Equivalently, some box
has at most \left\lfloor n/m \right\rfloor.)
The proof is a one-line proof by
contradiction: if every box held at most
\lceil n/m \rceil - 1 objects, the total would be at most
m\left(\lceil n/m \rceil - 1\right) < n — fewer than
n objects, contradicting that we placed all n.
So some box must exceed the average. That is the whole engine: you cannot beat the average
everywhere.
Worked examples — the surprising ones
Two people with the same number of friends
In any group of n \ge 2 people (where friendship is mutual),
two people have exactly the same number of friends within the group. Each person's
friend-count is one of 0, 1, \dots, n-1 — that is
n possible "holes" for n people, which is not yet
a squeeze. The twist: 0 and n-1 cannot both occur
(if someone is friends with everyone, nobody has zero friends). So really only
n-1 counts are possible for n people — pigeonhole
forces a repeat.
A pair summing to a round number
Choose any 6 integers from 1 to
10. Two of them must sum to 11. Pair up the ten
numbers by their sum: \{1,10\}, \{2,9\}, \{3,8\}, \{4,7\}, \{5,6\} — five
boxes. Six chosen numbers into five boxes forces two into the same box, and each box is a pair summing
to 11. The art is always in choosing the boxes: the
pigeonhole step is trivial once the right pigeonholes are named.
Long division always repeats
Why is every fraction's decimal expansion eventually periodic? Dividing by
q, each step produces a remainder in
\{0, 1, \dots, q-1\} — only q possibilities. Do
more than q steps and a remainder must recur; from that point the whole
long-division process repeats verbatim, so the digits cycle. Pigeonhole explains a fact you have known
since school.
The generalised principle in action
To guarantee k objects in some box, you need more than
m(k-1) objects — spread m(k-1) perfectly and every
box has exactly k-1; one more forces a k-stack. So
the threshold is m(k-1) + 1.
Among any m(k-1) + 1 objects placed into
m boxes, some box contains at least k of them —
and m(k-1) objects is not enough.
To be sure of 3 cards of the same suit you draw
4 \cdot 2 + 1 = 9 cards from a standard deck
(m = 4 suits, k = 3). To be sure of
2 people sharing a birth month you need
12 \cdot 1 + 1 = 13 people. The formula is just "fill every box to the brim,
then add one".
Pigeonholing works on measurements, not just objects. Put 5 points
anywhere inside a 1 \times 1 square; two of them are within
\frac{\sqrt2}{2} \approx 0.707 of each other. Cut the square into four
\tfrac12 \times \tfrac12 cells (the boxes); five points into four cells
forces two into the same small cell, whose diagonal — the greatest possible distance inside it — is
\sqrt{(1/2)^2 + (1/2)^2} = \frac{\sqrt2}{2}. This "chop the space into
cells" idea is the seed of Dirichlet's approximation theorem and a whole branch of geometry.
-
Pigeonhole proves existence, never location. It guarantees some box
overflows but names none. Do not try to read off which — that is not what the principle
gives you.
-
Name the boxes deliberately. The whole difficulty is inventing the right holes
(remainders, sums, suits, sub-squares). The counting step is trivial; the modelling step is the
skill.
-
Off-by-one at the threshold. Forcing a repeat among m
boxes needs m + 1 objects, not m; forcing
k needs m(k-1)+1. Exactly
m(k-1) can still be spread thin.