The first formalization of the idea is believed to have been made by Johann Dirichlet[1] 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"), Italian ("principio dei cassetti") and German ("Schubfachprinzip").
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.
Softball team
Imagine five people who want to play softball (n = 5 items), with a limitation of only four softball teams (m = 4 holes) to choose from. A further limitation is imposed in the form of each of the five refusing to play on a team with any of the other four players. It is impossible to divide five people among four teams without putting two of the people on the same team, and since they refuse to play on the same team, by asserting the pigeonhole principle it is easily deducible that at most four of the five possible players will be able to play.
Sock-picking
Assuming that in a box there are 10 black socks and 12 blue socks, calculate the maximum number of socks needed to be drawn from the box before a pair of the same color can be made. Using the pigeonhole principle, to have at least one pair of the same color (m = 2 holes, one per colour) using one pigeonhole per color, you need only three socks (n = 3 items). In this example, if the first and second sock drawn are not of the same color, the very next sock drawn would complete at least one same-color pair (m = 2).
Hand-shaking
If there are n number of people who can shake hands with one another (where n > 1), the pigeonhole principle shows that there is always a pair of people who will shake hands with the same number of people. As the 'holes', or m, correspond to number of hands shaken, and each person can shake hands with anybody from 0 to n − 1 other people, this creates n − 1 possible holes. This is because 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; likewise, if one person shakes hands with no one there cannot be a person who shakes hands with everybody). This leaves n people to be placed in at most n − 1 non-empty holes, guaranteeing duplication.
The birthday problem
The birthday problem asks that, in a set of n randomly chosen people, what is the probability that some pair of them will have the same birthday. If there are 367 people in the room, we know that there is at least one pair who share the same birthday, as there are only 366 possible birthdays to choose from.
The pigeonhole principle also arises in computer science.
[1]Johann Peter Gustav Lejeune Dirichlet (1805 –1859) was a German mathematician with deep contributions to number theory (including creating the field of analytic number theory), as well as to the theory of Fourier series and other topics in mathematical analysis; he is credited with being one of the first mathematicians to give the modern formal definition of a function.
No comments:
Post a Comment