Basic Pigeonhole Principle

Combinatorics · Axiom Academy

LESSON Basic Pigeonhole Principle A fundamental counting principle that appears simple yet leads to powerful results Let's begin with the precise mathematical formulation of the Pigeonhole Principle. This can also be stated more generally: if kn+1 objects are placed into n boxes, at least one box must contain at least k+1 objects. We prove the Pigeonhole Principle using proof by contradiction. 3. Application: Hair Count in a City A classic application demonstrates the power of this simple principle. Problem: In any city with more than 200,000 people, at least two people have the same number of hairs on their head. A human head has at most approximately 200,000 hairs (this is generous - most people have much fewer) So the possible hair counts are: 0, 1, 2, ..., 200,000 (that's 200,001 possibilities) If we have more than 200,000 people, we have at least 200,001 people Think of each possible hair count as a "box" and each person as an "object" By the Pigeonhole Principle, at least two people must have the same hair count! 4. Application: Consecutive Integer Subsets Here's a more mathematical application involving subsets and divisibility. Problem: Given any n integers, show that some subset of them has a sum divisible by n. Let the integers be a₁, a₂, ..., aₙ. Consider the partial sums: If any Sᵢ is divisible by n, we're done. Otherwise, each Sᵢ has a remainder when divided by n, and these remainders must be from 1, 2, ..., n-1 .

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