We put $15$ balls into $5$ boxes. No box can contain more than $4$ balls. Prove that there are at least $3$ boxes, containing $3$ or more balls.

Question

We put $15$ balls into $5$ boxes. No box can contain more than $4$ balls. Prove that there are at least $3$ boxes, containing $3$ or more balls.

I know this problem is crying to be solved by the pigeonhole principle. However I couldn't figure how to apply it exactly and started looking into cases (which turned out to be a lot). How can one apply the pigeonhole principle properly to this problem? Thanks in advance.

Answer 1

This method is tedious but straight forward:

Suppose there are NO boxes containing three or more balls. Then every box contains no more then 2 balls. There cannot be more than 2(5)= 10 balls, not 15.

If only one box contains 3 or more balls then we have four boxes containing at most 2 balls and one containing at most four balls. There cannot be more than 2(4)+ 4= 12 balls, not 15.

If only one two boxes contains 3 or more balls then we have three boxes containing at most 2 balls and two containing at most four balls. There cannot be more than 2(3)+ 2(4)= 14 balls, not 15.