If you have more items than containers, you are guaranteed a collision

If you have more items than containers, you are guaranteed a collision
Image: Intellect (generated)

In short: The pigeonhole principle is a deceptively simple mathematical rule: if you distribute more objects than you have available slots, at least one slot must hold multiple items. While it sounds like common sense, this counting argument is a powerful tool for proving complex results in mathematics and computer science.

First documented in 1622 by Jean Leurechon, the principle is often named after Peter Gustav Lejeune Dirichlet, who popularized it in 1834. Though the term 'pigeonhole' evokes images of birds, it actually refers to the small, open-fronted compartments in traditional desks or cabinets used for sorting mail. The concept is essentially a statement about the impossibility of an injective function when the domain is larger than the codomain.

The principle’s utility spans from the trivial to the profound. For instance, in a city like London with over 9 million residents, we can mathematically guarantee that thousands of people share the exact same number of hairs on their heads, as the number of people far exceeds the biological upper limit of human hair counts. Similarly, it explains why lossless data compression is physically impossible for every possible input: if you try to map a larger set of data to a smaller set of storage values, collisions are inevitable.

Beyond simple sorting, the principle underpins sophisticated concepts like hashing in computer science, where it dictates that hash tables cannot guarantee unique codes for every input. It even aids in proving theorems in mathematical analysis, such as finding specific integer approximations for irrational numbers. Whether applied to handshakes, birthdays, or tournament teams, the principle provides a rigorous foundation for understanding why certain overlaps are not just possible, but mathematically certain.

While the principle confirms that an overlap exists, it remains silent on the frequency or distribution of those collisions. It establishes the existence of a shared container, but leaves the deeper statistical analysis of how many items land in each slot to the field of probability. Despite its simple premise, it remains a cornerstone of discrete mathematics, proving that even in a vast world, some patterns are unavoidable.

Opens the Intellect+ feed with this card first. Swipe up for the next one.

Sources

To cite this card, link to https://intellectplus.co.uk/app/science-pigeonhole-principle.

How we source, check and correct cards: Editorial standards.

General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.

Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?

Related

Finding something worth knowing…