A basic principle of
discrete math that is used quite often in theoretical
computer science. This is one of those things where you think to yourself, "Why did anyone bother to right this down in a book?"
The Pigeon-hole Principle If k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects. -- Rosen, Kenneth H.; Discrete Mathematics and its Applications, Third Edition