TheoremProved

The generalized pigeonhole principle

Statement

If $n$ objects are distributed into $k$ boxes, then some box contains at least $\lceil n/k\rceil$ objects.

Why is it true?

The basic principle only guarantees $2$ objects somewhere; the generalized version sharpens this to the exact minimum forced by averaging $n$ objects over $k$ boxes, using the same contradiction idea but comparing against $\lceil n/k\rceil-1$ instead of $1$ .

Proof sketch

Assume, for contradiction, that every box contains at most $\lceil n/k\rceil-1$ objects.

Then the total number of objects distributed is at most $k\left(\lceil n/k\rceil-1\right)$ .

Since $\lceil n/k\rceil$ is the smallest integer at least $n/k$ , we have $\lceil n/k\rceil-1<n/k$ , so $k\left(\lceil n/k\rceil-1\right)<k\cdot\frac{n}{k}=n$ .

So the total distributed is strictly less than $n$ , contradicting that all $n$ objects were distributed. Hence some box contains at least $\lceil n/k\rceil$ objects.

Topics that use this theorem

The pigeonhole principle

Step-by-step proofs

No step-by-step proof yet for this theorem.