Pigeonhole principle
A finite assignment forces a shared output when inputs outnumber outputs.
Key knowledge
For finite sets A and B with |A|>|B|, every total function f:A→B maps two distinct elements of A to the same element of B.
Conditions and scope
- The function must assign every input to one output.
- This is an existence conclusion, not a procedure identifying the colliding inputs.
Sources · 2
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
- Mathematics for Computer Science (2015), 14.8: Pigeonhole principleEric Lehman, F. Thomson Leighton and Albert R. Meyer / MIT OpenCourseWareTextbook chapter · PDF
- Discrete Mathematics; Probability and Statistical Methods · COR 4.1Audrija Choudhury and Arun Sarkar, University of Kalyani DODLTeaching resource · PDF
Evidence and review
A finite assignment forces a shared output when inputs outnumber outputs.
2026-10-10 · Independent Physics and Measurement reference editor (AI editorial bounded review). Exact bounded introductory reference claims and this practical concept inventory are approved after closure. Existing university/research proof and source scopes remain separate; no universal knowledge-completeness or experimental-validation assertion.
Foundational review
2026-10-10 · Independent AI editorial inspection of this new compact reference entry, its equations, applicability, sources and knowledge connections.
Sources from other places
Agreement within this scope
More objects than boxes forces some box to contain at least two.
The finite-function repository form is the same counting argument.
University of Kalyani, Directorate of Open and Distance Learning; Heramba Chandra College
- Discrete Mathematics; Probability and Statistical Methods · COR 4.1 IndiaEnglish
§10.6 Theorem 10.6.1, printed p.91 (PDF p.101)
- Discrete Mathematics; Probability and Statistical Methods · COR 4.1
Entry details
Permanent link to this entry ↗- Record identity
- foundation-math-pigeonhole-principle
- Revision
- foundations-audit.1
- Structured reference record
- Foundational core completion