Skip to content
Omnikalc

Pigeonhole principle calculator: the fullest box, the emptiest box and the items needed to guarantee a target

Enter the number of items, the number of boxes and a target to get the guaranteed minimum in one box, the maximum in another and the items needed to be sure of the target.

Updated on
Your inputs

Value out of range

Value out of range

Value out of range

Results

Some box holds at least

5

Some box holds at most
4
Items needed to guarantee the target in one box
61
More items needed to guarantee the target
8
Items beyond the guarantee (surplus)
0

The pigeonhole principle says that when you put items in boxes, some box must hold a minimum number of items. The pigeonhole principle calculator gives the guaranteed minimum in the fullest box, the maximum in the emptiest and the items needed to guarantee a target in one box.

How the calculation works

  • Enter the number of items (such as people) and the number of boxes (such as the months of the year).
  • Enter the target: the number of items that you want to be sure to find in the same box.
  • The calculator gives the guaranteed minimum in the fullest box, ⌈n / k⌉, and the maximum in the emptiest box, ⌊n / k⌋.
  • It also finds the number of items needed to guarantee the target, k × (m − 1) + 1, and how many more items are needed.

Example

Among 53 people, there are 12 months of birth. Some month holds at least ⌈53 / 12⌉ = 5 people, and some month holds at most ⌊53 / 12⌋ = 4. To be sure that 6 people share a month, you need 12 × (6 − 1) + 1 = 61 people, so 8 more are needed.

Why it matters

The calculator helps students of discrete mathematics, teachers, programmers who think about hash collisions, and puzzle lovers. It gives quickly the answer to questions like how many people are needed to be sure that some share a birth month or how many socks to take to get a pair.

Good to know

The principle gives a guarantee, which is the worst case, and it does not tell what usually happens. For probabilities, as in the birthday problem, a different calculation is needed. The calculator assumes that every item goes to exactly one box and that you do not know how the items are distributed.

The combinations calculator counts the choices of items, the permutations calculator counts ordered arrangements, the birthday paradox calculator finds the probability of a shared birthday, and the derangements calculator counts arrangements with no item in its place.

Frequently asked questions

What is the pigeonhole principle?

The pigeonhole principle says that if you put n items into k boxes and n is larger than k, at least one box contains more than one item. The general form says that at least one box contains at least ⌈n / k⌉ items. For example, among 13 people, at least two were born in the same month.

How many items do I need to be sure of m in one box?

To be sure that some box holds at least m items, you need k × (m − 1) + 1 items. With fewer items, all the boxes can hold m − 1 items and none reaches m, and the next item must make a box reach m. For 12 months and a target of 6, you need 12 × 5 + 1 = 61 people.

What is the difference between the fullest and the emptiest box?

The principle also gives a bound in the other direction: at least one box holds at most ⌊n / k⌋ items. If the items cannot be shared perfectly, the fullest box holds at least ⌈n / k⌉ and the emptiest at most ⌊n / k⌋. When k divides n, the two numbers are equal and the best case is a perfect share.

Does the principle say which box is full?

No. It proves that such a box exists, but it does not say which one. This is why the principle is so useful in proofs about existence, in computer science for hash collisions, and in everyday puzzles like finding two socks of the same color or two people with the same number of friends.

Was this calculator helpful?

Thanks for your feedback!

Results are estimates provided for information purposes. They do not replace professional advice.