materiały: Pigeonhole principle

This seemingly obvious statement, a type of counting argument, can be used to demonstrate possibly unexpected results.

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. For example, of three gloves, at least two must be right-handed or at least two must be left-handed, because there are three objects but only two categories of handedness to put them into. This seemingly obvious statement, a type of counting argument, can be used to demonstrate possibly unexpected results. For example, given that the population of London is more than one unit greater than the maximum number of hairs that can be on a human head, the principle requires that there must be at least two people in London who have the same number of hairs on their heads. Although the pigeonhole principle appears as early as 1622 in a book by Jean Leurechon, it is commonly called Dirichlet's box principle or Dirichlet's drawer principle after an 1834 treatment of the principle by Peter Gustav Lejeune Dirichlet under the name Schubfachprinzip ("drawer principle" or "shelf principle"). The principle has several generalizations and can be stated in various ways. In a more quantified version: for natural numbers k and m, if n = km + 1 objects are distributed among m sets, the pigeonhole principle asserts that at least one of the sets will contain at least k + 1 objects. For arbitrary n and m, this generalizes to k + 1 = ⌊ ( n −…

Kategoria: materiały

Rodzina: materiały

Jakość źródła: 65/100

Próby weryfikacji: 0

Notatka fact-checku: Verification queue initialized; Fact-check 2.50+ owns subsequent state transitions.