The pigeonhole principle states that if you have eleven letters to put in ten pigeonholes, then at least one pigeonhole will contain at least two letters. Although this seems like an obvious enough statement, this counting principle can nevertheless be used to prove some rather non-obvious facts. It is a basic and important tool in the field of combinatorics.

The formal phrasing of the pigeonhole principle is as follows. Suppose N and R are finite sets containing n and r elements respectively, where n > r. Suppose f is a function from N into R (thus f "puts n elements into at most r pigeonholes"). Then there is some element a of R whose preimage contains at least [n/r] elements (where [n/r] denotes the ceiling function). Recall that the preimage of a is the collection of all elements in N that are sent to a...