Simple Applications of the Pigeonhole Principle
What you'll learn: You'll apply the Pigeonhole Principle to solve real-world problems involving birthdays, handshakes, and selection scenarios.
Core Idea in Plain English
Now that you understand the Pigeonhole Principle's statement and intuition, let's put it to work! The principle states: if you have more pigeons than pigeonholes, at least one pigeonhole must contain more than one pigeon. This simple idea unlocks solutions to problems that might otherwise seem difficult.
Classic Applications
The Birthday Problem (Simplified)
Question: In a room of 13 people, must at least two people share a birth month?
Solution: Think of 12 pigeonholes (the months) and 13 pigeons (the people). Since 13 > 12, by the Pigeonhole Principle, at least one month must contain at least two birthdays. Yes, guaranteed!
The Handshake Problem
Question: At a party with 5 people, each person shakes hands with some others. Is it possible that everyone shook a different number of hands?
Solution: Each person can shake 0, 1, 2, 3, or 4 hands (5 possibilities for 5 people). But wait—if someone shook 0 hands, no one could have shaken 4 hands (everyone). So really, there are only 4 possible values. With 5 people and 4 pigeonholes, at least two people must have shaken the same number of hands!
Selection from a Set
Question: If you select 5 numbers from {1, 2, 3, 4, 5, 6, 7, 8}, must at least two numbers sum to 9?
Solution: Create pigeonholes: {1,8}, {2,7}, {3,6}, {4,5}—pairs that sum to 9. With 4 holes and 5 selections, you must pick two numbers from the same pair, which sum to 9!
Key Takeaway: The Pigeonhole Principle transforms existence questions into counting arguments—identify your "pigeons" and "pigeonholes," then let the principle guarantee your conclusion.