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