Pigeonhole Problem Examples

Combinatorics · Axiom Academy

EXAMPLE Pigeonhole Problem Examples Master the pigeonhole principle through step-by-step worked examples Show that in a group of 367 people, at least 2 people must share the same birthday (ignoring leap years). Excellent work! You've completed these pigeonhole principle examples. Here's what we learned: Identify the mapping: The first step is always to identify what represents the "pigeons" (objects being placed) and what represents the "pigeonholes" (categories or containers). Compare quantities: If you have n pigeonholes and more than n pigeons, at least one pigeonhole must contain at least 2 pigeons. If you have n pigeonholes and more than k·n pigeons, at least one pigeonhole must contain at least k+1 pigeons. Generalized principle: The pigeonhole principle guarantees existence but doesn't tell you which specific pigeonhole will have multiple pigeons. Real-world applications: This principle appears in birthday problems, sock matching, divisibility proofs, geometry problems, and computer science algorithms. Proof by contradiction: Many pigeonhole proofs work by assuming all pigeonholes have at most one pigeon, then showing this leads to a contradiction. The pigeonhole principle is deceptively simple but incredibly powerful. Practice identifying pigeons and pigeonholes in various contexts to master this technique!

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