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
| Situation | Items | Boxes | Guarantee |
|---|---|---|---|
| Birth months | 13 people | 12 months | Two share a month |
| Birthdays | 367 people | 366 possible dates (including February 29) | Two share a birthday |
| Socks in the dark (only black and white) | 3 socks drawn | 2 colors | A matching pair |
| Class grades | 100 students | 5 letter grades | At least 20 share a grade |
| Hair on heads | Millions of people in a big city | Possible 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.
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.
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
- Friendship Paradox Explained: Why Friends Have More Friends
- Survivorship Bias Explained: Examples and WWII Planes
- Regression to the Mean Explained (With Examples)
Sources and Further Reading
Related to This Article
More math articles
- How to Solve Word Problems by Adding Three or More Fractions
- The Challenge for The Future of Math Education
- Public Goods: Vertical Summation vs. Private Demand
- Ecclesia, Church, Denomination, Sect, and New Religious Movement
- 5 Best Mini Laptops to Use Anytime, Anywhere
- The Best Grade 4 ELA Practice Tests for Massachusetts Students
- A Comprehensive Collection of FREE ACT Math Practice Tests
- Pregnancy Calculator
- The Significance of the Unit Circle in Trigonometric Functions
- How to Navigate the Fraction Jungle: A Guide to Adding Fractions with Unlike Denominators


What people say about "Pigeonhole Principle Explained: Formula and Examples - Effortless Math"?
No one replied yet.