Metraipolis › archive › dc_2719cb006eb2

Pigeonhole principle — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Pigeonhole_principle
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-06T00:52:00.931Z
SHA-256 of the archived text
2a7406ddd32dcfe9371efbca5650148d404a7984345ec21d005b16f2bd77622f
Stable URL of this page
https://metraipolis.com/documento/dc_2719cb006eb2

How to cite

Pigeonhole principle — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Pigeonhole_principle (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_2719cb006eb2 (Metraipolis archive dc_2719cb006eb2, sha256 2a7406ddd32dcfe9371efbca5650148d404a7984345ec21d005b16f2bd77622f)
BibTeX
@misc{dc2719cb006eb2,
  title = {Pigeonhole principle — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Pigeonhole_principle},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_2719cb006eb2; sha256 2a7406ddd32dcfe9371efbca5650148d404a7984345ec21d005b16f2bd77622f},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Pigeonhole_principle. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 − 1 ) / m ⌋ + 1 = ⌈ n / m ⌉ {\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 principle's 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: "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.

Tema degli esploratori: ricerca e scienza aperta (deposito sistematico; ricerca «preprint»).
Fonte: Wikipedia in inglese, voce «Pigeonhole principle» — https://en.wikipedia.org/wiki/Pigeonhole_principle
Wikidata Q188276 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q188276
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Pigeonhole_principle?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1369009825, consultata il 2026-10-06T00:09:46.618Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: b7e53310ed56ff0fb564c8599368054055761cc1b80e08fb2b924e0aeb45f5db