Pigeonhole Principle

Book: A Walk through Combinatorics

Pigeonhole principle:

Let nn and kk be positive integers and let n>kn \gt k. Suppose we have to place nn identical balls into kk boxes. At least one box will need to contain at least 2 balls.

Proof (by contradiction):

Let's assume there is no box with more than 1 ball. Thus each box has either 0 or 1 ball in it. Let the number of boxes with 0 balls be mm; m0m \geq 0.

Thus, there are kmk - m boxes which have 1 ball in them.

Thus we've only placed kmk - m balls into boxes

Now, kmk<nk - m \leq k \lt n. Therefore we haven't placed all nn balls. Hence if we want to place all nn balls, our initial assumption must be falsified, and we need to have at least one box with more than 1 ball.