# Pigeonhole Principle

**Type:** Concept  
**Domain:** Discrete Mathematics  
**Also known as:** Dirichlet's box/drawer principle  
**Codex URL:** /mathematics/discrete/pigeonhole-principle/  
**Entry status:** Live — v1.0 (2026-05-27)

## Summary
If n+1 items are placed in n containers, some container has 2+. Simple but powerful proof technique.

## Generalised version
n items in k containers → some container has ≥⌈n/k⌉ items.

## Classic examples
- 367 people guarantee a shared birthday (366 possible days)
- Two NYC residents with identical hair count (max ~200,000 hairs, millions of people)

## Erdős–Szekeres theorem (1935)
Any sequence of n²+1 distinct reals contains an increasing or decreasing subsequence of length n+1.

## Repeating decimals
Long division of p/q: only q possible remainders — one must repeat within q+1 steps, forcing digit repetition.

## Dirichlet's approximation theorem (1842)
For irrational α, fractions p/q exist with |α−p/q|<1/(qN) for q≤N.

## Computer science
Hash function collisions are unavoidable (pigeonhole); birthday attack in cryptography exploits this.

## Naming history
Attributed to Dirichlet (1830s-40s); German "Schubfachprinzip" (drawer principle).

## Sources
### Tier 1
- Graham, R.L., Knuth, D.E. and Patashnik, O. (1994). *Concrete Mathematics*. 2nd ed.
- Erdős, P. and Szekeres, G. (1935). *Compositio Mathematica*.
### Tier 2
- Graham, R.L., Rothschild, B.L. and Spencer, J.H. (1990). *Ramsey Theory*. 2nd ed.

---
*Mathematics Codex entry v1.0 — added 2026-05-27 — thecodex.expert/mathematics/*