--- title: "The Pigeonhole Principle" description: "Use the observation that more objects than boxes forces a repeat to prove existence results no construction would give." canonical: https://lightmysky.com/learn/mathematics/the-pigeonhole-principle-mt_wgfpmZqzd9 source: https://lightmysky.com/learn/mathematics/the-pigeonhole-principle-mt_wgfpmZqzd9.md retrieved: 2026-09-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # The Pigeonhole Principle Use the observation that more objects than boxes forces a repeat to prove existence results no construction would give. Subject: Mathematics · Area: Discrete Mathematics · Ages 19 to 20 Page: https://lightmysky.com/learn/mathematics/the-pigeonhole-principle-mt_wgfpmZqzd9 ## Ready when they can - State the principle and its generalised form with a ceiling - Choose the pigeons and the holes for a stated problem, which is the whole difficulty - Prove a result such as two people in a group sharing a handshake count ## Lesson: More pigeons than holes forces a repeat If you have more objects than boxes, some box must hold two. Four socks into three colours force two socks to share a colour. Thirteen people force two to share a birth month, since twelve months are the boxes. Sorting into boxes proves the result with no construction at all. The generalised form sharpens the promise with a ceiling. With m objects in n boxes, some box holds at least m over n rounded up. Ten pigeons in 3 holes force 4 in one hole, since 10 over 3 rounds up to 4. The ceiling is sharp: one fewer object can always dodge, since 2 per hole absorbs 8 pigeons across 4 holes. **Example.** Choosing the pigeons and the holes is the whole difficulty. With 5 people, handshake counts look like 0 to 4, but 0 and 4 exclude each other: if someone shook none, nobody shook all. That leaves 4 live holes for 5 people, so two share a count. Choosing 7 numbers from 1 to 12 works the same way: the six complementary pairs summing to 13 are the holes, so one pair gives both members. **Tip.** Name your containers before you count anything. Ask what is plentiful and what is scarce, then assign pigeons to the many and holes to the few. Five socks can dodge across five colours with one each, so the sixth sock forces the match. In birthday arguments, people are the pigeons and months are the holes. **Recap.** Name your containers first, then let overfill do the proving. ## Practice 18 questions on this page, each with its working shown. ## Needs first - [Binomial Coefficients and Combinatorial Identities](https://lightmysky.com/learn/mathematics/binomial-coefficients-and-combinatorial-identities-mt_lHXFvudTh6) - [Proof by Contradiction and Counterexample](https://lightmysky.com/learn/mathematics/proof-by-contradiction-and-counterexample-mt_pbFTv4v6k8) ## Opens up - [Inclusion-Exclusion](https://lightmysky.com/learn/mathematics/inclusion-exclusion-mt_MgU-IMpVHA)