October 7, 2025

What Is The Pigeonhole Principle

Q: Is the pigeonhole principle also called something else?

Yes, it is often referred to as Dirichlet's box principle or the drawer principle, named after the mathematician Peter Gustav Lejeune Dirichlet who formalized the concept.

Q: What is the generalized pigeonhole principle?

The generalized version states that if you place 'n' items into 'm' containers, then at least one container must hold at least ⌈n/m⌉ items, where ⌈x⌉ is the ceiling function (the smallest integer greater than or equal to x).

Q: How can you use this principle to prove two people in London have the same number of hairs on their heads?

The average human head has about 150,000 hairs, and it's safe to assume no one has more than 1 million hairs. The number of 'pigeonholes' is the number of possible hair counts (0 to 1,000,000). The population of London (the 'pigeons') is over 8 million. Since there are more people than possible hair counts, at least two people must have the exact same number of hairs.

Q: Does the principle tell you which pigeonhole has extra pigeons?

No, it does not. The pigeonhole principle is an existence proof; it proves that a situation must exist (a shared pigeonhole) without identifying which specific one it is.

Discover the pigeonhole principle, a fundamental concept in mathematics that explains why if you have more items than containers, at least one container must hold more than one item.

Have More Questions →

Defining the Pigeonhole Principle

The pigeonhole principle is a simple but powerful concept in mathematics stating that if you have 'n' items to place into 'm' containers, and the number of items (n) is greater than the number of containers (m), then at least one container must contain more than one item. The items are often referred to as 'pigeons' and the containers as 'pigeonholes'.

Section 2: The Core Logic

The principle is a fundamental counting argument. It doesn't specify which container will have multiple items or exactly how many it will contain. It only guarantees the existence of such a container. The logic is that if you were to place one pigeon in each pigeonhole, you would run out of holes before you run out of pigeons, forcing the remaining pigeons to share a hole that is already occupied.

Section 3: A Practical Example

Imagine you are in a dark room with a drawer containing red socks and blue socks. To guarantee you have a matching pair, you only need to pull out three socks. The 'pigeonholes' are the two colors (red and blue). By picking three socks (the 'pigeons'), the principle ensures that at least two of them must be the same color, giving you a matching pair.

Section 4: Importance and Applications

Despite its simplicity, the pigeonhole principle is widely used in proofs across various fields of mathematics, such as number theory and combinatorics. In computer science, it is essential for analyzing hashing algorithms, as it proves that hash collisions (where two different inputs produce the same output) are inevitable if the number of possible inputs exceeds the number of possible hashes.

Frequently Asked Questions

Is the pigeonhole principle also called something else?

What is the generalized pigeonhole principle?

How can you use this principle to prove two people in London have the same number of hairs on their heads?

Does the principle tell you which pigeonhole has extra pigeons?