Math, asked by shivanishekhar91622, 8 months ago

State and prove Pigeonhole principle with an example.​

Answers

Answered by shristisingh952
4

pigeonhole principle states that if {\displaystyle n} items are put into {\displaystyle m} containers, with {\displaystyle n>m}then at least one container must contain more than one item.[1] In layman's terms, if you have more "objects" than you have "holes," at least one hole must have multiple objects in it. A real-life example could be, "if you have three gloves, then you have at least two right-hand gloves, or at least two left-hand gloves," because you have 3 objects, but only two categories to put them into (right or left). This seemingly obvious statement, a type of counting argument, can be used to demonstrate possibly unexpected results. For example, if you know that the population of London is greater than the maximum number of hairs that can be present on a human's head, then the pigeonhole 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 1624 in a book attributed to Jean Leurechon,[2] 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").[3]

The principle has several generalizations and can be stated in various ways. In a more quantified version: for natural numbers {\displaystyle k}

 and {\displaystyle m}, if {\displaystyle n=km+1} objects are distributed among {\displaystyle m} sets, then the pigeonhole principle assrts that at least one of the sets will contain at least {\displaystyle k+1} objects.[4] For arbitrary {\displaystyle n} and {\displaystyle m} this generalizes to {\displaystyle k+1=\lfloor (n-1)/m\rfloor +1=\lceil n/m\rceil ,}where {\displaystyle \lfloor \cdots \rfloor and {\displaystyle \lceil \cdots \rceil }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.

Step-by-step explanation:

mark me as brainliest....

Similar questions