Pigeonhole principle

From Wikipedia, the free encyclopedia

The inspiration for the name of the principle: pigeons in holes. Here n = 7 and m = 9 so we can conclude that there are at least two empty pigeonholes. (There would be three if exactly two birds shared one hole.)
The inspiration for the name of the principle: pigeons in holes. Here n = 7 and m = 9 so we can conclude that there are at least two empty pigeonholes. (There would be three if exactly two birds shared one hole.)

The pigeonhole principle, also known as Dirichlet's box (or drawer) 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 ("drawer principle" or "shelf principle"). In Italian too, the original name "principio dei cassetti" is still in use; in some other languages (for example, Russian) this principle is called the Dirichlet principle (not to be confused with the minimum principle for harmonic functions of the same name).

Contents

[edit] Examples

An easy example of the pigeonhole principle involves the situation when there are five people who want to play softball (n = 5 objects), but there are only four softball teams (m = 4 holes). This would not be a problem except that each of the five refuses to play on a team with any of the other four. 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.

Although the pigeonhole principle may seem to be intuitive, it can be used to demonstrate possibly 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 (m = 1 million holes). There are more than 1,000,000 people in London (n is bigger than 1 million objects). 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 at least two people with the same number of hairs on their heads.

Another example is: Presume that in a box there are 10 black socks and 12 blue socks and you need to get one pair of socks of the same colour. Supposing you can take socks out of the box only once and only without looking, how many socks do you have to pull out together? The correct answer is three. To have at least one pair of the same colour (m = 2 holes, one per colour), using one pigeonhole per colour, you need only three socks (n = 3 objects). In this example, if the first and second sock drawn are not of the same colour, the very next sock drawn would complete at least one same-colour pair. (m = 2)

If there are n persons (at least two) who can arbitrarily shake hands with one another, there is always a pair of persons who shake hands with the same number of people. Here, the 'holes' correspond to number of hands shaken. Each person can shake hands with anywhere from 0 to n − 1 other people. This creates n possible holes, but either the '0' or the 'n − 1' hole must be empty (if one person shakes hands with everybody, it's not possible to have another person who shakes hands with nobody, and vice versa). This leaves n people to be placed in at most n − 1 non-empty holes, guaranteeing duplication.

The pigeonhole principle often arises in computer science. For example, collisions are inevitable in a hash table because the number of possible keys exceeds the number of indices in the array. No hashing algorithm, no matter how clever, can avoid these collisions. This principle also proves that any lossless compression algorithm that makes at least one input file smaller will make some other input file larger. (Otherwise, two files would be compressed to the same smaller file and restoring them would be ambiguous.)

A notable problem in Mathematical Analysis where the pigeonhole principle shows up, is for a fixed irrational number a, to show that the set {[na]: n is an integer} of fractional parts is dense in [0,1]. After a moments thought, one finds that it is not easy to explicitly find integers n, m such that |na - m| < e, where e > 0 is a small positive number and a is some arbitrary irrational number. But if you take M such that 1/M < e, by the pigeonhole principle there must be n1, n2 in {1, 2, ..., M + 1} such that n1*a and n2*a are in the same integer subdivision of size 1/M (there are only M such subdivisions between consecutive integers). In particular, we can find n1, n2 such that n1*a is between (p + k/M, p + (k+1)/M), and n2*a is between (q + k/M, q + (k+1)/M), for some p,q integers and k in {0, 1, ..., M - 1}. We can then easily verify that (n2 - n1)*a is between (q-p - 1/M, q-p + 1/M). This implies that [n*a] < 1/M < e, where n = n2 - n1 or n = n1 - n2. This shows that 0 is a limit point of {[na]}. We can then use this fact to prove the case for p in (0,1]: find n such that [na] < 1/M < e, then if p in (0,1/M], we are done. Otherwise p in (j/M, (j+1)/M], and by setting k = sup{r in N: r*[na] < j/M}, you get |[(k+1)na] - p| < 1/M < e.

Several additional examples are given by Grimaldi (see References).

[edit] Generalizations of the pigeonhole principle

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 \lceil n/m \rceil objects, where \lceil x\rceil is the ceiling function, denoting the smallest integer larger than or equal to x.

A probabilistic generalization of the pigeonhole principle states that if n pigeons are randomly put into m pigeonholes with uniform probability 1/m, then at least one pigeonhole will hold more than one pigeon with probability

1 - \frac{m!}{(m-n)!\;m^n} = 1 - \frac{(m)_n}{m^n}, \!

where (m)n is a falling factorial. For n = 0 and for n = 1 (and m > 0), that probability is zero; in other words, if there is just one pigeon, there cannot be a conflict. For n > m (more pigeons than pigeonholes) it is one, in which case it coincides with the ordinary pigeonhole principle. But even if the number of pigeons does not exceed the number of pigeonholes (n ≤ m), due to the random nature of the assignment of pigeons to pigeonholes there is often a substantial chance that clashes will occur. For example, if 2 pigeons are randomly assigned to 4 pigeonholes, there is a 25% chance that at least one pigeonhole will hold more than one pigeon; for 5 pigeons and 10 holes, that probability is 69.76%; and for 10 pigeons and 20 holes it is about 93.45%. This problem is treated at much greater length at birthday paradox.

[edit] Infinite sets

The pigeonhole principle can be extended to infinite sets by considering infinite cardinal numbers. Cantor's diagonal argument provides a relatively simple demonstration of this. Infinite cardinals have counterintuitive properties — for instance, Hilbert's Grand Hotel can accommodate more guests without doubling up on rooms even when it is already full. This because the set of rooms and the set of guests have the same cardinality, namely ℵ0.

[edit] References

[edit] See also

[edit] External links