Pigeonhole Principle

This principle says that if you distribute n items among k containers, then at least one container must contain at least the average number of items, rounded up. It works because if every container had fewer than \u230a n/k \u2309? Actually, if every container had at most one less than the ceiling, the total would fall short of n, so that is impossible. In other words, uneven distribution forces one container to reach or exceed the ceiling of n/k.

Use it whenever you need to guarantee that some group, box, day, person, or category has a minimum count without knowing the exact distribution. It is common in counting, scheduling, graph theory, and "at least one must..." proof problems.

• Using floor instead of ceiling, which gives a value that is too small
• Forgetting that the guarantee is "at least one container," not that every container has that many
• Applying the rule without correctly identifying what counts as an item and what counts as a container