Pigeonhole Principle Calculator

What Is the Pigeonhole Principle?

The pigeonhole principle — also known as Dirichlet's box principle or the drawer principle — is one of the most elegant and broadly applicable theorems in combinatorics and discrete mathematics. In its simplest form it states: if n items are placed into k containers and n > k, then at least one container must hold more than one item.

The name evokes a classic image: if you have 10 pigeons and only 9 pigeonholes (the compartmented wall-mounted boxes historically used to sort mail), at least one pigeonhole must contain 2 or more pigeons. Despite its apparent simplicity, the principle underlies surprisingly deep results in number theory, graph theory, and computer science.

The Generalized Pigeonhole Principle

The generalized pigeonhole principle extends the basic statement to any threshold m. If n items are distributed into k containers, then at least one container holds at least ⌈n/k⌉ items (where ⌈ ⌉ denotes the ceiling function, rounding up to the nearest integer).

Equivalently, to guarantee that at least one container holds m or more items, you need at least:

N = k(m − 1) + 1

The logic is airtight: with k(m−1) items you could distribute exactly m−1 per container, with no container reaching m. The very next item — the (k(m−1)+1)-th — must go into some container, pushing it to m items.

Historical Background — Dirichlet's Box Principle

The principle was formalized by German mathematician Peter Gustav Lejeune Dirichlet around 1834, who called it the Schubfachprinzip (drawer principle). Dirichlet used it to prove deep results in Diophantine approximation — specifically, that for any real number α and integer N, there exist integers p and q with 1 ≤ q ≤ N such that |α − p/q| < 1/(qN). This is the fundamental theorem of Diophantine approximation.

Despite being a nineteenth-century formalization, applications of the principle appear implicitly in even earlier mathematical work. The "pigeonhole" metaphor itself is an English-language coinage that became standard in the twentieth century.

Applications in Number Theory

The pigeonhole principle has powerful applications across number theory:

• Rational approximation (Dirichlet): For any irrational α and integer N ≥ 1, there exist integers p, q with 0 < q ≤ N and |qα − p| < 1/N. The proof partitions the N+1 fractional parts {0}, {α}, {2α}, …, {Nα} into N intervals of length 1/N — by pigeonhole, two must fall in the same interval.
• Schur's theorem: For any r-coloring of the integers {1, 2, …, N} (for large enough N), there exist positive integers x, y, z of the same color with x + y = z. The proof uses a pigeonhole argument over color classes.
• Ramsey theory: R(3,3) = 6 means any 2-coloring of the edges of K₆ contains a monochromatic triangle. The proof is a direct application of pigeonhole applied to the 5 edges incident to any vertex.
• Perfect squares: Any set of n+1 integers from {1, 2, …, 2n} contains two that are consecutive (pigeonhole over pairs {1,2}, {3,4}, …, {2n-1,2n}).

Applications in Computer Science

• Hash collisions: Any hash function mapping a larger input space to a smaller output space must produce collisions. If a hash function produces 32-bit outputs (2³² possible values) but can process files of any size, then the moment you have more than 2³² distinct files, some pair must share a hash. This is why cryptographic hash functions are designed to make collisions computationally hard to find, not impossible.
• Lossless compression limits: No lossless compression algorithm can compress all inputs. If it compressed every file of length n bits to fewer bits, there would be more source files than compressed representations — impossible by pigeonhole. Some files must be unchanged or lengthened.
• Graph coloring lower bounds: In a graph where the maximum degree is Δ, the chromatic number is at most Δ+1 (greedy coloring), and certain dense subgraph structures force a higher chromatic number by pigeonhole arguments.
• Sorting lower bounds: Any comparison-based sorting algorithm requires at least ⌈log₂(n!)⌉ comparisons in the worst case. The argument uses pigeonhole over the decision tree of comparisons.

The Birthday Paradox Connection

The pigeonhole principle tells us that 367 people in a room guarantee (with 100% certainty) that at least two share a birthday (since there are at most 366 distinct birthdays). This is a hard threshold.

The famous birthday paradox is a probabilistic cousin: with only 23 people, the probability that some pair shares a birthday exceeds 50%. With 70 people, this probability exceeds 99.9%. The "paradox" is that people underestimate how quickly the probability of a collision grows as the group size increases.

The two results address different questions: pigeonhole gives a certainty bound (worst-case guarantee), while the birthday paradox gives a probabilistic bound (average-case behavior). Both are important tools in cryptographic analysis — the birthday attack on hash functions exploits the probabilistic result.

Reference Table — Common Pigeonhole Applications

Scenario	Items (n)	Containers (k)	Guarantee (m)	Minimum Needed
Same birthday (day)	people	366	2	367
3 share birthday (day)	people	366	3	733
Same birth month	people	12	2	13
Same weekday birthday	people	7	2	8
Matching sock pair	socks	k colors	2	k + 1
2 cards same suit	cards	4	2	5
3 cards same suit	cards	4	3	9