Pigeonhole principle
Guarantee a repeated placement without identifying which box receives it.
Pigeonhole principle is one of 1 counting formula in the discrete math section of this library, and it is used at high school · university level.
Why pigeonhole principle works
Suppose every box held fewer objects than the stated ceiling. Then the grand total would come to less than N, contradicting the fact that all N objects were placed somewhere. So at least one box must reach that ceiling, and the argument needs no information about how the objects were spread.
What each symbol means
$N$ is the object count and $k$ the nonempty collection of boxes.
Pigeonhole principle: when it holds
$N\ge0$ and $k>0$ are integers.
When it stops applying
It gives no useful information when N is smaller than k. With 5 objects in 12 boxes the ceiling comes out as 1, which just says some box holds at least one object, and that was obvious before you started.
Pigeonhole principle: a worked example
Among $13$ people, at least $\lceil13/12\rceil=2$ share a birth month.
The mistake to avoid
What people do: Students name a specific box, saying the crowded one must be the first or the largest.
Why it goes wrong: The argument proves only that some box is crowded; it gives no way to identify which one. Different arrangements can put the crowd anywhere.
Do this instead: State the conclusion the way the principle does, that at least one box holds that many. With 13 people and 12 months, some month has 2 or more birthdays, but nothing says which month.
Pigeonhole principle: step by step
- Name the unknown, and the unit the answer has to come out in.
- Match the symbols to your values. $N$ is the object count and $k$ the nonempty collection of boxes.
- Check the conditions before substituting. $N\ge0$ and $k>0$ are integers.
- Substitute, keep exact values to the last line, then test the sign, size, and unit against a rough estimate — the check that catches most discrete math slips.
Where this formula fits
- Subject
- Discrete Math formulas — 11 entries in this library
- Topic
- Counting
- Level
- High school · University
Formulas are easiest to keep when they sit inside a method rather than on a list. Use the links below to see where pigeonhole principle comes from, to check a calculation against a tool, and to practise it until you can recall it without looking.
- Probability Foundations — the lesson behind this formula: model outcomes, complements, and conditional information.
- Discrete Math Calculator — check your substitution and the value it produces.
- Study discrete math — the subject guide that explains the ideas these formulas compress.
- Discrete Math Practice — questions that make you retrieve the formula instead of recognising it.
- All 11 discrete math formulas — the full grouped reference, or the complete formula library.
Questions about pigeonhole principle
Why the ceiling instead of ordinary rounding?
Because you need a guaranteed floor on the crowded box, and rounding down would claim less than is certain. With 13 objects in 12 boxes the average is 1.08, but the guarantee is a whole 2.
How many people guarantee that three share a birth month?
Twenty-five. With 24 you could have exactly 2 per month and no trio, but the twenty-fifth person has to join a month that already holds 2.
Does it tell me how many boxes are crowded?
No, only that at least one is. It is a pure existence statement, which is what makes it so easy to apply and so limited in what it delivers.
What is a surprising use of it?
Any group of 367 people must contain two with the same birthday, since there are at most 366 possible dates. No information about the people is needed, which is the principle's whole charm.