Some counting questions ask for a guarantee rather than a count: how many socks must you grab to be sure of a pair? The answer comes from a principle so simple it sounds obvious, yet it settles surprising questions. It is a fact about functions between finite sets, and it is usually combined with the sum and product rules.
Key idea
Pigeonhole principle: if more than $n$ items go into $n$ boxes, some box gets at least two. More generally, if more than $kn$ items go into $n$ boxes, some box gets at least $k + 1$; with $N$ items, some box gets at least $\lceil N/n \rceil$. To find the number that guarantees an outcome, find the largest number that can still avoid it (the worst case) and add one.
Why it works
Prove it by contrapositive: if every box held at most $k$ items, the total would be at most $kn$. So more than $kn$ items force a box above $k$. In function language: a function from a bigger finite set to a smaller one cannot be one-to-one. Two inputs must share an output.
Worked examples
Worked example: Socks in the dark
A drawer has many socks in $4$ colors. How many must you take, without looking, to be sure of two of the same color? Three of the same color?
- Two: the worst case is one of each color, $4$ socks with no pair. The next sock must match: $5$.
- Three: the worst case is two of each color, $8$ socks. The next one makes three of some color: $9$.
Answer: $5$ and $9$
Worked example: Birth months
Among $100$ people, what is the largest number you can be sure share a birth month?
- $12$ months are the boxes. If each month had at most $8$ people, there would be at most $96$ people.
- So some month has at least $\lceil 100/12 \rceil = 9$.
- And $9$ is the best guarantee: the people could be spread with $8$ or $9$ in each month.
Answer: $9$
Worked example: Pairs that add to $11$
Show that among any $6$ numbers chosen from $\{1, 2, \ldots, 10\}$, two add up to $11$.
- Make $5$ boxes, the pairs that add to $11$: $\{1, 10\}, \{2, 9\}, \{3, 8\}, \{4, 7\}, \{5, 6\}$.
- $6$ numbers in $5$ boxes: some box receives two numbers, and those two add to $11$.
- With only $5$ numbers it can fail: $1, 2, 3, 4, 5$.
Answer: $6$ numbers always contain such a pair.
Common mistake
Finding the number that makes something possible instead of the number that guarantees it. With $4$ colors, $2$ socks might match, but nothing is certain until $5$. Check: build the worst case on purpose, the largest set of items that avoids the goal, and confirm that one more item cannot avoid it. The answer is the worst case plus one.