TheoremProved

The basic pigeonhole principle

Statement

If $n$ objects are distributed into $k$ boxes with $n>k$ , then at least one box contains at least $2$ objects.

Why is it true?

This is really a statement about counting, proved by assuming the opposite and reaching a contradiction: if every box had at most $1$ object, the boxes could not hold more than $k$ objects in total.

Proof sketch

Assume, for contradiction, that the conclusion fails: every one of the $k$ boxes contains at most $1$ object.

Then the total number of objects distributed is at most $k\times1=k$ .

But we distributed $n$ objects, and $n>k$ by hypothesis, so the total number of objects distributed is $n>k$ .

These two counts of the same set of objects contradict each other ( $n>k$ but also total $\le k$ ), so the assumption was false: some box must contain at least $2$ objects.

Topics that use this theorem

The pigeonhole principle

Step-by-step proofs

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