I decided to do some more research on the Pigeonhole Principle. It is also known as Dirichlet's box. This principle states that, given two natural numbers n and m with n > m, if n items are put into m pigeonholes, then at least one pigeonhole must contain more than one item. Another way of stating this would be that m holes can hold at most m objects with one object to a hole; adding another object will force one to reuse one of the holes, provided that m is finite. More formally, the theorem states that there does not exist an injective function on finite sets whose codomain is smaller than its domain.
−
−
The pigeonhole principle is an example of a counting argument which can be applied to many formal problems, including ones involving infinite sets that cannot be put into one-to-one correspondence. In Diophantine approximation the quantitative application of the principle to the existence of integer solutions of a system of linear equations goes under the name of Siegel's lemma.
−
−
The first statement of the principle is believed to have been made by Dirichlet in 1834 under the name Schubfachprinzip. In Italian too, the original name "principio dei cassetti" is still in use; in some other languages this principle is called the Dirichlet principle.
