Pigeonhole principle

In mathematics, the pigeonhole principle states that if n {displaystyle n} items are put into m {displaystyle m} containers, with n > m {displaystyle n>m} , then at least one container must contain more than one item. This theorem is exemplified in real life by truisms like 'in any group of three gloves there must be at least two left gloves or at least two right gloves'. It is an example of a counting argument. This seemingly obvious statement can be used to demonstrate possibly unexpected results; for example, that there must be (at least) two people in London who have the same number of hairs on their heads. In mathematics, the pigeonhole principle states that if n {displaystyle n} items are put into m {displaystyle m} containers, with n > m {displaystyle n>m} , then at least one container must contain more than one item. This theorem is exemplified in real life by truisms like 'in any group of three gloves there must be at least two left gloves or at least two right gloves'. It is an example of a counting argument. This seemingly obvious statement can be used to demonstrate possibly unexpected results; for example, that there must be (at least) two people in London who have the same number of hairs on their heads. 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 or Dirichlet's drawer principle. The principle has several generalizations and can be stated in various ways. In a more quantified version: for natural numbers k {displaystyle k} and m {displaystyle m} , if n = k m + 1 {displaystyle n=km+1} objects are distributed among m {displaystyle m} sets, then the pigeonhole principle asserts that at least one of the sets will contain at least k + 1 {displaystyle k+1} objects. For arbitrary n {displaystyle n} and m {displaystyle m} this generalizes to k + 1 = ⌊ ( n − 1 ) / m ⌋ + 1 = ⌈ n / m ⌉ , {displaystyle k+1=lfloor (n-1)/m floor +1=lceil n/m ceil ,} where ⌊ ⋯ ⌋ {displaystyle lfloor cdots floor } and ⌈ ⋯ ⌉ {displaystyle lceil cdots ceil } denote the floor and ceiling functions, respectively. 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 whose codomain is smaller than its domain'. Advanced mathematical proofs like Siegel's lemma build upon this more general concept. Dirichlet published his works in both French and German, using either the German Schubfach (he wrote about distributing pearls), or the French tiroir. The strict original meaning of both corresponds to the English drawer, an open-topped box that can be slid in and out of the cabinet that contains it. These terms were morphed to the word pigeonhole, standing for a small open space in a desk, cabinet, or wall for keeping letters or papers, metaphorically rooted in the structures that house pigeons. Since Dirichlet's father was a postmaster, and furniture with pigeonholes is commonly used for storing or sorting things into many categories (like letters in a post office or room keys in a hotel), the translation pigeonhole may be a perfect rendering of Dirichlet's metaphor. That understanding of the word, referring to some furniture features, is fading —especially among those who do not speak English natively but as a lingua franca in the scientific world— in favour of the more pictorial interpretation, literally involving pigeons and holes. The suggestive, though not misleading interpretation of 'pigeonhole' as 'dovecote' has lately found its way back to a German back-translation of the 'pigeonhole'-principle as the 'Taubenschlag'-principle. Besides the original terms 'Schubfach-Prinzip' in German and 'Principe des tiroirs' in French, other literal translations are still in use in Polish ('zasada szufladkowa'), Bulgarian ('принцип на чекмеджетата'), Turkish ('çekmece ilkesi'), Hungarian ('skatulyaelv'), Italian ('principio dei cassetti'), Dutch ('ladenprincipe '), Danish ('Skuffeprincippet'), Persian ('اصل لانه کبوتری'), Chinese ('抽屉原理'), and Japanese ('引き出し論法'). Assume a drawer contains a mixture of black socks and blue socks, each of which can be worn on either foot, and that you are pulling a number of socks from the drawer without looking. What is the minimum number of pulled socks required to guarantee a pair of the same color? Using the pigeonhole principle, to have at least one pair of the same color (m = 2 holes, one per color) using one pigeonhole per color, you need to pull only three socks from the drawer (n = 3 items). Either you have three of one color, or you have two of one color and one of the other. If there are n 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. In this application of the principle, the 'hole' to which a person is assigned is the number of hands shaken by that person. Since each person shakes hands with some number of people from 0 to n − 1, there are n possible holes. On the other hand, either the '0' hole or the 'n − 1' hole or both must be empty, for it is impossible (if n > 1!) for some person to shake hands with everybody else while some person shakes hands with nobody. This leaves n people to be placed into at most n − 1 non-empty holes, so that the principle applies.