|
The pigeonhole principle states that if n pigeons are put into m pigeonholes, and if
n > m, then at least one pigeonhole must contain more than one pigeon. 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 you to
reuse one of the holes. The first statement of the principle is believed to have been made by Dirichlet in 1834 under the name Schubfachprinzip ("drawer principle"). In some languages (for example, Russian)
this principle is therefore called the Dirichlet principle (not to be confused with the minimum principle for harmonic functions of the same name).
Although the pigeonhole principle may seem to be a trivial observation, it can be used to demonstrate unexpected results. For
example, there must be at least two people in London with the same number of hairs on their heads. Demonstration: a
typical head of hair has around 150,000 hairs. It is reasonable to assume that no-one has more than 1,000,000 hairs on their
head. There are more than 1,000,000 people in London. If we assign a pigeonhole for each number of hairs on a head, and assign
people to the pigeonhole with their number of hairs on it, there must be two people with the same number of hairs on their
heads.
Another practical example of the pigeonhole principle involves the situation when there are five people who want to play
softball, but only four teams. This wouldn't be a problem except that each of the five refuses to play on a team with any of the
other 4. To prove that there is no way for all five people to play softball, the pigeonhole principle says that it is impossible
to divide five people among four teams without putting two of the people on the same team. Since they refuse to play on the same
team, at most four of the people will be able to play.
A generalized version of this principle states that, if n discrete objects are to be allocated to m
containers, then at least one container must hold no fewer than objects, where denotes the ceiling function.
The pigeonhole principle is an example of a counting argument which
can be applied to many more serious 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.
See also
- cardinal number
- Ramsey's theorem
|