Principle of the drawers

In Mathematical, the principle of the drawers affirms that if N socks occupy m drawers, and if N > m , then at least a drawer must contain strictly more than one sock. Another formulation would be that m drawers cannot contain strictly more m socks with only one sock per drawer; to add another sock will oblige to re-use one of the drawers.

Mathematically, the principle of drawers can be stated as follows:

If E and F is two Ensemble S finished, such as card ( E ) > card ( F ) and if F : E → F is a Application of E in F, then it exists an element of F which admits at least two antecedents by F .

Or:

If E and F is two finished units, such as card ( E ) > card ( F ) and if F : E → F is an application of E in F, then F is not injective; in other words, there does not exist injective mapping of E in F .

Name

The first version of the principle was stated by Dirichlet in 1834 under the name of Schubfachprinzip (“principle of the drawer”), following an observation of its socks in its convenient. In certain countries like Russia, this principle is called the principle of Dirichlet (not to be confused with the Principe of the maximum for the harmonic functions, of the same name). This principle is also called principle of the drawers of Dirichlet-Schläfli , or principle of the boxes , or by literary translation of English the principle of the holes of pigeons . In this last image, one replaces sock by egg of pigeon and drawer by nest of pigeon!

Applications

Although the principle of the drawers seems to be a completely unimportant observation, it can be employed to show unexpected results.

For example, there must be at least two people in Dallas in Texas with the same number of hair on their head. Demonstration: a normal head has approximately 150.000 hair and it is reasonable to suppose that nobody has more than 1.000.000 of hair on the head. There is more than 1.000.000 people in Dallas. If we associate with each number of hair on a head a drawer, and if we place each inhabitant of Dallas in the drawer corresponding to his number of hair on the head, then according to the principle of the drawers, there are necessarily at least two people having exactly the same number of hair on the head in Dallas! Obviously, the result remains true for any megalopolis.
Donnons another example of application of the principle of the drawers in the situation where there are five people who want to play Rugby, but only four teams. It would not be a problem if each of the five people did not refuse to play in a team with one unspecified of the four others. To show that there is no means so that each of the five people play Rugby, we apply the principle of the drawers which indicates that it is impossible to divide five people in four teams without putting two players in the same team. Since the players refuse to play in the same team, at most four players will be able to play.

Approximation of a reality

That is to say a reality X and a natural entirety N . For any reality there , one notes $\ {there \}$ the fractional part of there . The $(n+1)$ elements of $defined by 0, \ {X \}, \ dowries, \ {nx \} are distributed in the n " tiroirs" [q/n, (q+1) /n [, where q=0, \ ldots, n-1 . There thus exists an entirety q and two entireties 0 \ Leq k such as:$

\ frac {Q} {N} \ Leq \ {kx \} \ Leq \ {lx \} < \ frac {q+1} {N}.

By noting

p

the difference of the whole parts of

kx

and

lx

, one from of deduced:

|(l-k) x-p|< \ frac {1} {N},

or, by introducing the entirety

q=l-k

, lower than

n

\ left|X \ frac {p} {Q} \ right|< \ frac {1} {q^2}.

Generalizations

A generalized version of this principle declares that, if N discrete objects occupy m containers, then at least a container must contain at least $P \ left (\ frac {N} {m} \ right)$ objects where P is the function which associates with a reality X the smallest entirety equal to or higher than X . The number $P \ left (\ frac {N} {m} \ right)$ is thus the smallest entirety equal to or higher than $\ frac {N} {m}$ , and can be written with the function whole Partie: $-E \ left (- \ frac {N} {m} \ right)$ .

The principle of the drawers is an example of argument of enumeration. This principle can be applied to many serious problems, including those which imply infinite units which cannot be put in univocal correspondence. In Approximation diophantienne, the quantitative application of the principle shows the existence of whole solutions of a system of linear equations and this result bears the name of lemma of Siegel .

See too

Random links: