Generalized Pigeonhole Principle

Combinatorics · Axiom Academy

LESSON Generalized Pigeonhole Principle A powerful extension that quantifies exactly how many objects must share a property Before stating the generalized principle, we need to understand the ceiling function denoted by ⌈x⌉. ⌈3.2⌉ = 4 (smallest integer ≥ 3.2) ⌈7.9⌉ = 8 (smallest integer ≥ 7.9) 2. The Generalized Pigeonhole Principle This generalizes the classical principle beautifully: If n = k + 1 and we have k boxes, then ⌈(k+1)/k⌉ = ⌈1 + 1/k⌉ = 2, recovering the classical statement If n = 10 and k = 3, then ⌈10/3⌉ = ⌈3.33...⌉ = 4, so some box has at least 4 objects If n = 100 and k = 7, then ⌈100/7⌉ = ⌈14.28...⌉ = 15, so some box has at least 15 objects We prove the generalized pigeonhole principle using proof by contradiction. The generalized pigeonhole principle has numerous practical applications:

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