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.
Related tools
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.