Book: A Walk through Combinatorics
Let and be positive integers and let . Suppose we have to place identical balls into 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 ; .
Thus, there are boxes which have 1 ball in them.
Thus we've only placed balls into boxes
Now, . Therefore we haven't placed all balls. Hence if we want to place all balls, our initial assumption must be falsified, and we need to have at least one box with more than 1 ball.