Pigeonhole Principle
See: Data Key Collision, Hash Table.
References
2013
- http://en.wikipedia.org/wiki/Pigeonhole_principle
- In mathematics, the pigeonhole principle states that if n items are put into m pigeonholes with n > m, then at least one pigeonhole must contain more than one item. This theorem is exemplified in real-life by truisms like "there must be at least two left gloves or two right gloves in a group of three gloves". It is an example of a counting argument, and despite seeming intuitive it can be used to demonstrate possibly unexpected results; for example, that two people in London have the same number of hair on their heads (see below).
The first formalization of the idea is believed to have been made by Peter Gustav Lejeune Dirichlet in 1834 under the name Schubfachprinzip ("drawer principle" or "shelf principle"). For this reason it is also commonly called Dirichlet's box principle, Dirichlet's drawer principle or simply "Dirichlet principle" — a name that could also refer to the minimum principle for harmonic functions. The original "drawer" name is still in use in French ("principe des tiroirs"), Polish ("zasada szufladkowa"), Hungarian ("skatulyaelv"), Italian ("principio dei cassetti"), German ("Schubfachprinzip"), Danish ("Skuffeprincippet"), and Chinese ("抽屉原理").
Though the most straightforward application is to finite sets (such as pigeons and boxes), it is also used with infinite sets that cannot be put into one-to-one correspondence. To do so requires the formal statement of the pigeonhole principle, which is "there does not exist an injective function on finite sets whose codomain is smaller than its domain". Advanced mathematical proofs like Siegel's lemma build upon this more general concept.
- In mathematics, the pigeonhole principle states that if n items are put into m pigeonholes with n > m, then at least one pigeonhole must contain more than one item. This theorem is exemplified in real-life by truisms like "there must be at least two left gloves or two right gloves in a group of three gloves". It is an example of a counting argument, and despite seeming intuitive it can be used to demonstrate possibly unexpected results; for example, that two people in London have the same number of hair on their heads (see below).