Pigeonhole Principle Explained: Formula and Examples

Quick answer: The pigeonhole principle says that if more objects are placed into boxes than there are boxes, at least one box must contain two or more objects. For example, among 13 people at least two share a birth month, because there are only 12 months. The generalized version: if N objects go into k boxes, some box holds at least N ÷ k objects, rounded up. The boxes can be months, categories, remainders or any possible outcomes.

Facts checked November 22, 2026.

Some of the most powerful ideas in mathematics sound almost too obvious to say. The pigeonhole principle is the champion: if 10 pigeons fly into 9 pigeonholes, some hole gets at least two pigeons. Yet this one sentence proves facts that seem impossible to check, from hair counts in a city to the limits of file compression. Here is how it works, with examples you can verify yourself.

The Principle in Two Versions

Simple version. If \(n + 1\) or more items are placed into \(n\) boxes, at least one box contains two or more items.

General version. If \(N\) items are placed into \(k\) boxes, at least one box contains at least \(\lceil N/k \rceil\) items, where \(\lceil \ \rceil\) means “round up.”

Why it is true: if every box held at most one item, the boxes would hold at most \(n\) items in total, but there are \(n + 1\). That contradiction is the whole proof.

How to Use the Generalized Pigeonhole Principle

The formula \(\lceil N/k \rceil\) gives the guaranteed minimum in the fullest box. For example, 100 students and 12 birth months give \(\lceil 100/12 \rceil = \lceil 8.33 \rceil = 9\): if every month had at most 8 students, there could be only \(12 \times 8 = 96\) students, but there are 100.

To work backward, use this rule. To guarantee at least \(r\) objects in one of \(k\) boxes, you need

\[ N = k(r – 1) + 1. \]

To guarantee that at least 4 students share a birth month: \(12 \times 3 + 1 = 37\). With 36 students, every month could have exactly 3; the 37th forces a fourth. The formula gives the smallest number that guarantees the result, not the count in every box.

Try it: Pigeonhole Calculator

Everyday Examples

SituationItemsBoxesGuarantee
Birth months13 people12 monthsTwo share a month
Birthdays367 people366 possible dates (including February 29)Two share a birthday
Socks in the dark (only black and white)3 socks drawn2 colorsA matching pair
Class grades100 students5 letter gradesAt least 20 share a grade
Hair on headsMillions of people in a big cityPossible hair counts (well under a million)Two people with exactly the same number of hairs

The hair example is a classic. Assume every resident has fewer than 1,000,000 hairs (a typical head has far fewer), so each hair count is one of the numbers 0 to 999,999: one million boxes. A city such as London has millions of residents, more than one million, so at least two residents must have exactly the same number of hairs, even though no one could ever count them.

Surprising Proofs

1. Two People at Any Party Have the Same Number of Friends There

In a group of \(n\) people (with \(n \ge 2\)), each person has between 0 and \(n – 1\) friends in the group. That looks like \(n\) possible values for \(n\) people. But 0 and \(n – 1\) cannot both happen: if someone is friends with everyone, nobody has zero friends. So there are only \(n – 1\) possible values for \(n\) people, and two people must share a value.

2. Two Numbers Whose Difference Is Divisible by 10

Among any 11 whole numbers, two have a difference divisible by 10. The boxes are the 10 possible last digits (remainders 0 to 9 when dividing by 10). Eleven numbers, ten remainders: two numbers \(a = 10q + r\) and \(b = 10s + r\) share a remainder, so \(a – b = 10(q – s)\).

3. Five Points in a Square

Place 5 points anywhere in a square with side 2. Divide it into four smaller squares with side 1, assigning points on a dividing line to either neighboring square. Five points, four small squares: two points land in the same small square, so they are at most its diagonal apart, \(\sqrt{2} \approx 1.41\).

4. A Repeating Pattern in Every Fraction

Why does \(1/7 = 0.142857142857\ldots\) repeat? In long division by 7, each step leaves a remainder. If a remainder is ever 0, the decimal stops. Otherwise each remainder is one of 1 to 6, so within 7 steps a remainder must repeat, and from then on the digits repeat. The same argument shows every fraction has a terminating or repeating decimal.

5. Multiples Made Only of 1s and 0s

For any whole number \(n\), some multiple of \(n\) is written using only the digits 1 and 0. Look at the \(n + 1\) numbers 1, 11, 111, …, up to the one with \(n + 1\) ones. There are only \(n\) possible remainders when dividing by \(n\), so two of them share a remainder. Subtract the smaller from the larger: the result is a multiple of \(n\), and it looks like 111…1000…0.

Why No Compressor Can Shrink Every File

The pigeonhole principle sets a hard limit in computer science. There are \(2^n\) different files that are exactly \(n\) bits long. The number of files shorter than \(n\) bits is

\[ 2^0 + 2^1 + \cdots + 2^{n-1} = 2^n – 1, \]

one fewer. A lossless compressor must turn different files into different outputs (otherwise it could not decompress them). So it cannot map all \(2^n\) files into the \(2^n – 1\) shorter ones: at least one file fails to get smaller. Real compressors, and the AI models used to compress text, work because real data has patterns; they make some files larger to make typical files smaller.

Hash Collisions and AI Systems

Computers often turn data into short fixed-length codes called hashes, used for passwords, databases and checking downloads. A 256-bit hash has \(2^{256}\) possible values, but there are far more possible inputs, so by the pigeonhole principle different inputs must sometimes share a hash. Security depends on collision resistance: making such collisions practically impossible to find, not impossible to exist. The same reasoning applies whenever AI systems squeeze huge inputs into fixed-size representations: information must be lost or shared somewhere.

Pigeonhole Principle vs the Birthday Paradox

The pigeonhole principle gives guarantees: 367 people must include a shared birthday. The birthday paradox is about probability: with just 23 people, the chance of a shared birthday is already about 50%. One tells you what must happen; the other tells you what is likely. See the birthday paradox explained.

Who Discovered the Pigeonhole Principle?

The principle is commonly associated with the German mathematician Peter Gustav Lejeune Dirichlet, which is why it is also called Dirichlet’s box principle; in German it is the Schubfachprinzip (“drawer principle”). The often-repeated date of 1834 lacks a precise citation; historians find Dirichlet’s published uses in 1842. Historians Benoît Rittaud and Albrecht Heeffer found that it appears much earlier, in a 1622 French book attributed to the Jesuit Jean Leurechon, which already used the hairs-on-heads argument.

Common Misconceptions

“It tells you which box has two items.” No. It proves a box exists, without saying which one.

“23 people guarantee a shared birthday.” No. 23 people give about a 50% chance; a guarantee needs 367 people.

“24 students guarantee three share a birth month.” No. Each month could have exactly 2; you need \(12 \times 2 + 1 = 25\).

“It only works for small numbers.” It works for any size, including huge sets like all possible files or hashes.

“Equal numbers of items and boxes force a repeat.” No. You need more items than boxes.

Watch: The Pigeonhole Principle in Action

If you learn better by watching, these videos are worth your time.

What Is the Pigeonhole Principle? (Spanning Tree). A clear animated introduction with classic examples.
Simple Principle Solves Seemingly IMPOSSIBLE Math Problems (Up and Atom). Surprising proofs that use nothing but the pigeonhole principle.

Check Your Understanding

Five quick questions to see how much of this has stuck. Pick an answer and press Submit; you will see a short explanation either way.

Answer each question and press Submit to see your result right away.

1. What is the fewest people needed to guarantee two share a birth month?
Found a bug? Let us know!
2. 100 students receive one of 5 grades. At least how many share a grade?
Found a bug? Let us know!
3. What is the fewest students needed to guarantee 4 share a birth month?
Found a bug? Let us know!
4. Why can no lossless compressor shrink every file?
Found a bug? Let us know!
5. 21 objects go into 5 boxes. What is guaranteed?
Found a bug? Let us know!

Frequently Asked Questions

What is the pigeonhole principle in simple words?

If you have more items than boxes, at least one box must contain more than one item. For example, 13 people must include two who share a birth month.

What is the generalized pigeonhole principle?

If N items are placed in k boxes, at least one box contains at least N divided by k items, rounded up. For example, 100 items in 5 boxes means some box has at least 20.

Who discovered the pigeonhole principle?

It is commonly associated with Peter Gustav Lejeune Dirichlet, whose published uses date to 1842, but historians have found it in a 1622 French book attributed to Jean Leurechon.

What is an example of the pigeonhole principle in computer science?

No lossless compression method can shrink every file, and every hash function must have collisions, because there are more possible inputs than outputs.

How do you find how many objects guarantee r in one box?

Use N = k(r − 1) + 1, where k is the number of boxes. For example, 37 people guarantee that at least 4 share a birth month.

Is the birthday paradox the same as the pigeonhole principle?

No. The pigeonhole principle guarantees a shared birthday with 367 people. The birthday paradox is about probability: with just 23 people, the chance of a shared birthday is about 50%.

Keep Exploring

Sources and Further Reading

Related to This Article

What people say about "Pigeonhole Principle Explained: Formula and Examples - Effortless Math"?

No one replied yet.

Leave a Reply