Pigeonhole Principle Calculator
Apply the pigeonhole principle: find the guaranteed fullest container ⌈n/k⌉ items, and the items needed to force a container to a target count.
How it works
fullest ≥ ⌈n / k⌉ · to force m in one container you need k·(m − 1) + 1 items
The pigeonhole principle says that if n items go into k containers, at least one container must hold at least ⌈n/k⌉ items — you cannot spread them so evenly that every container stays below the ceiling. Turned around, to guarantee some container reaches m items you need k·(m−1)+1 of them, because k·(m−1) items could sit one-below-target everywhere before the next one tips a container over. It underpins surprising existence proofs, from shared birthdays to matching hair counts.
Worked example
Put 10 items into 3 containers: ⌈10/3⌉ = 4, so some container must hold at least 4. To guarantee 3 in one container you need 3×(3−1)+1 = 7 items.
Sources: Pigeonhole principle — Wikipedia
Frequently asked questions
What does the ceiling function do here?
It rounds n/k up to the next whole number, because containers hold whole items. With 10 items in 3 containers, 10/3 ≈ 3.33 rounds up to 4 guaranteed in the busiest one.
Why k·(m−1)+1 to force m items?
You could place m−1 items in every one of the k containers — that is k·(m−1) items — without any reaching m. The very next item must push some container to m.
What is a classic use of this?
In any group of 13 people, at least two share a birth month: 13 pigeons, 12 months, so ⌈13/12⌉ = 2 forces a shared month.
Related calculators
This calculator is for educational purposes. Double-check important results before acting on them.