# Solution

Prove that if $kn+1$ pigeons are placed into $n$ pigeon-holes, then at least one pigeon-hole must contain at least $k+1$ pigeons.

Let's try to argue by contradiction:

Assume that no pigeon-hole contains at least $k+1$ pigeons.

This means that each pigeon-hole contains at most $k$ pigeons. There are $n$ pigeon-holes, so there are at most $nk$ pigeons total in all of the pigeon-holes. However, this contradicts the given fact that $kn+1$ pigeons were placed into the $n$ pigeon-holes.

Hence, our assumption must be rejected, and the opposite must be true:

Some pigeon-hole must contain at least $k+1$ pigeons.

QED.