The Pigeonhole Principle
Simple version
If n+1 pigeons are distributed among n pigeonholes, one of the holes will contain at
least 2 pigeons.
Sophisticated version
If kn+1 objects are distributed among n classes, one of the classes will contain at least
k+1 objects.
Back to the problem