If n+1 pigeons fly into n holes, at least one hole has 2+ pigeons
Put more pigeons than holes and some hole has to hold two. It sounds too simple to matter, yet it settles problems that look impossible.
Drag the pigeons into the holes and try to avoid doubling up. Use the sliders to change the counts; with more pigeons than holes, you can’t.
Drag the pigeons into the holes. When you have more pigeons than holes, at least one hole must contain 2+ pigeons!
If n+1 objects are placed into n containers, at least one container must hold more than one object. This simple fact is surprisingly powerful in mathematics!
The Pigeonhole Principle is one of the simplest yet most powerful proof techniques in mathematics. If you have more pigeons than pigeonholes, at least one hole must contain multiple pigeons. Despite its simplicity, this principle underlies surprising results in combinatorics, number theory, and computer science.
The key to applying the principle is correctly identifying what the "pigeons" and "holes" represent in your problem. Once you find the right formulation, many "impossible" sounding problems become trivial.
Key insight: The Pigeonhole Principle proves existence without construction. We know a hole with 2+ pigeons must exist, but we cannot predict which one it will be.
Adjust the number of objects and containers, then run the animation and watch the guaranteed minimum per container.
If kn+1 objects are placed into n boxes, at least one box contains k+1 or more objects.
If kn+1 objects are distributed among n containers, at least one container must hold at least k+1 objects. This generalizes the basic principle (where k=1).
The extended principle: if kn+1 objects are distributed among n containers, at least one container holds k+1 or more objects. Adjust the parameters and see the guaranteed minimum per container.
Key insight: The generalized form is proved by contradiction. If every container held at most k objects, the total would be at most kn, which is less than kn+1. So at least one container must hold k+1.
Pick a problem, name the pigeons and the holes, and check your answers before revealing the solution.
Practice identifying the "pigeons" and "holes" in famous problems. This skill is key to applying the principle!
A drawer contains socks of 2 different colors (black and white). What is the minimum number of socks you must draw (without looking) to guarantee you have at least 2 socks of the same color?
Key insight: The creative step is choosing what counts as a "pigeon" and what counts as a "hole." The same problem can often be solved by different pigeonhole formulations.
Spot a mistake or have an idea?