The Pigeonhole Idea

Combinatorics · Axiom Academy

A simple principle that unlocks powerful mathematical proofs. Imagine you have some pigeons that need to go into pigeonholes. Use the slider to add more pigeons and watch what happens! You have a drawer with black and white socks mixed up. It's dark and you can't see the colors. How many socks do you need to pull out to guarantee a matching pair? How many people do you need in a room to guarantee that at least two share the same birth month? Add people and find out! If you distribute n + 1 objects into n containers, at least one container must contain at least 2 objects. This is called the Pigeonhole Principle (or Dirichlet's Drawer Principle). The pigeonhole principle proves that something exists without showing us what it is. We don't know which hole has multiple pigeons, but we know one must! This simple idea helps prove facts about prime numbers, graph theory, geometry, and even computer science. It's one of the most elegant tools in combinatorics!

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