Pigeonhole principle

The pigeonhole principle states that if n pigeons are put into m pigeonholes, and n > m, then at least one pigeonhole must contain more than one pigeon. Although this seems 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.

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 <math>\lceil n/m \rceil</math> objects, where <math>\lceil\dots\rceil</math> 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.

See also: cardinal number