Classic Applications

Combinatorics · Axiom Academy

Explore famous applications of the pigeonhole principle and learn how to identify the "pigeons" and "holes" in real problems Problem: At a party with 6 people, prove that at least two people must have shaken hands with the same number of others. Setup: Each person can shake hands with 0, 1, 2, 3, 4, or 5 others. That's 6 possible values. Wait... 6 people, 6 possible values. Where's the pigeonhole principle? Watch the animation to see the clever observation! Problem: In a city with 8 million people, prove that at least two people must have the same number of hairs on their head. Key Facts: The average human head has about 100,000 hairs. Even if we're generous and say no one has more than 1,000,000 hairs (they don't!), we can apply the pigeonhole principle. 3. Subset Sums (Modular Arithmetic) Problem: Given any 5 integers, prove that some subset of them has a sum divisible by 5. Strategy: Consider the cumulative sums and their remainders when divided by 5. This clever approach reveals a hidden pigeonhole structure! Problem: In a room with 13 people, prove that at least two people must have birthdays in the same month. This is one of the most straightforward applications of the pigeonhole principle, but it illustrates the core idea perfectly.

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