Pigeonhole Summary

Combinatorics · Axiom Academy

Let's review the key concepts from Unit 5: existence proofs, applications, and Ramsey theory. Simple Statement: If n + 1 objects are placed into n boxes, at least one box must contain at least 2 objects Contrapositive Form: If each of n boxes contains at most one object, then there are at most n objects total Proof Strategy: Proves existence without construction—guarantees something exists without finding it Key Insight: Forces conclusions based purely on counting, independent of how objects are distributed Generalized Pigeonhole Principle Statement: If n objects are placed into k boxes, at least one box contains at least ⌈n/k⌉ objects Ceiling Function: ⌈n/k⌉ rounds up to the nearest integer, ensuring the bound is always achievable When to Use: When you need to prove a box contains more than 2 objects, or establish minimum group sizes Common Applications: Birthday problem variants, substring repetitions, tournament results, and scheduling conflicts Example Recap: Classic Application Problem: Among any 13 people, prove that at least two were born in the same month Identify Objects and Boxes: Objects = 13 people, Boxes = 12 months of the year Apply Basic Principle: Since 13 > 12, we have n + 1 = 13 objects in n = 12 boxes Conclude: By the pigeonhole principle, at least one month (box) must contain at least 2 people (objects) Hair Counting: At least two people in a city have the same number of hairs (bounded count, large population)

This is the written version of the interactive lesson above. See the full Combinatorics course.