The pigeonhole principle states that if n+1 items are placed into n boxes, some box contains at least two items. Generalizations yield lower bounds and existence arguments across combinatorics, number theory, and CS.
Details
Concepts
Basic form: if m items in n boxes and m > n, then some box has ≥2 items.
General form: some box has at least ⌈m/n⌉ items (ceiling bound).
Applications: birthday paradox lower bound, collisions in hashing, Dirichlet’s approximation, Ramsey-style existence proofs.
Examples: two people in a city share initials; 13 people share a month; 7 integers yield two with difference divisible by 6.
Strengthening: probabilistic method often pairs with pigeonhole for stronger existence results.
Exercises
Hands-on
Show that among 367 people, two share a birthday. Generalize to n days.
Prove that in any set of 7 integers, two have difference divisible by 6.
Using ⌈m/n⌉, show that 100 socks in 3 colors imply 34 of some color.