In mathematics, the pigeonhole principle states that if n items are put into m containers, with n > m, then at least one container 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 hairs on their heads.

Since a typical human head has an average of around 150,000 hairs; it is reasonable to assume (as an upper bound) that no one has more than 1,000,000 hairs on their head (m = 1 million holes). There are more than 1,000,000 people in London (n is bigger than 1 million items). Assigning a pigeonhole to each number of hairs on a person’s head, and assign people to pigeonholes according to the number of hairs on their head, there must be at least two people assigned to the same pigeonhole by the 1,000,001st assignment (because they have the same number of hairs on their heads) (or, n > m).

*An image of pigeons in holes. Here there are n = 10 pigeons in m = 9 holes. Since 10 is greater than 9, the pigeonhole principle says that at least one hole has more than one pigeon.*

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’s principle”

Taken from http://en.wikipedia.org/wiki/Pigeonhole_principle

### Like this:

Like Loading...

*Related*