The pigeonhole principle, in its plainest form: if you place more than pigeons into holes, at least one hole contains more than one pigeon. It sounds trivial, but it's a genuine proof technique — it lets you guarantee that some collision, repeat, or coincidence must occur, without ever having to identify which one.
The generalized version
If items are placed into categories, at least one category contains at least items (the ceiling of , i.e. round up). This is the version that actually shows up on the AMC — the basic “more pigeons than holes” case is just the special case where you only need “more than 1.”
The hard part: choosing the holes
The real skill in pigeonhole problems is rarely the counting — it's figuring out what the holes should be. A classic move is to sort items by remainder when divided by some number, since that naturally creates a small, fixed number of categories (the possible remainders) for a much larger set of items.
Worked example
Problem: Show that among any 5 integers, some two of them have a difference divisible by 4.
Solution: Sort the 5 integers by their remainder mod 4. There are only 4 possible remainders (0, 1, 2, 3), so these act as 4 “holes.” With 5 integers going into 4 remainder classes, by pigeonhole at least one remainder class contains at least 2 of the integers. Those two integers are congruent mod 4, meaning their difference is divisible by 4.
Practice problems
1.If 13 people are in a room, show that at least two of them share a birth month.
2.What is the minimum number of people needed to guarantee that at least 3 of them share a birth month?
3.Show that among any 7 integers, some two have a sum or difference divisible by 10 (hint: pair up remainders and ).
4.A drawer has socks of 4 colors. What is the minimum number you must pull out (without looking) to guarantee a matching pair?