--- title: "The Pigeonhole Principle" description: "Use object counts and category capacities to prove that a repeat must exist, without necessarily finding the objects that repeat." 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-11-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 object counts and category capacities to prove that a repeat must exist, without necessarily finding the objects that repeat. 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 and apply the pigeonhole principle, its ceiling bound and capacity arguments - Choose objects and disjoint categories, including complementary pairs and remainder classes - Build a contradiction proof and explain why two handshake counts must agree ## Lesson: More pigeons than holes forces a repeat Assign each object to exactly one of n boxes, where n is a positive integer. Boxes may be empty. If objects outnumber boxes, some box contains at least two objects. The counts prove a repeat exists without naming its box. With no more objects than boxes, a repeat may occur, but the counts alone do not force it. Categories can act as boxes: a sock has one colour, and birth months give 12 categories. For m objects in n boxes, some box contains at least ceiling(m/n) objects. The ceiling is the smallest integer at least m/n. For example, 17 tokens in 5 boxes force at least 4 in some box. This does not mean every box holds 4, or that any box holds exactly 4. To force at least k in one box, the minimum total is n(k-1)+1: n(k-1) objects can be placed with k-1 in each box. *(drawing: Each row is one box's capacity. Five boxes hold at most 15 tokens if none holds 4. A sixteenth token exceeds that capacity.)* For a contradiction proof, set r = ceiling(m/n). Suppose every box holds at most r-1 objects. Their total is at most n(r-1). But r-1 < m/n, so n(r-1) < m, contradicting the total m. Capacity bounds also work by subtraction. If some boxes together hold at most C of the m objects, the remaining boxes together hold at least m-C. For n people, with n at least 2, count only handshakes within the group. Nobody shakes their own hand, and each pair shakes at most once. Counts range from 0 to n-1. These endpoints cannot both occur: someone who shook everyone also shook anyone said to have shaken nobody. If 0 occurs, n-1 is absent; otherwise 0 is absent. At most n-1 counts are available for n people, so two counts agree. *(drawing: If 0 is absent instead, only counts 1 through n-1 remain. Both cases give fewer count categories than people.)* To force a sum of 11, partition the integers 1 through 10 into five pairs: (1,10), (2,9), (3,8), (4,7), (5,6). Six distinct selections occupy five pair categories, so one category contains both members. Their sum is 11. Every integer belongs to exactly one pair. Distinctness matters: selecting one member repeatedly need not select its partner. *(drawing: The pairs are the holes. Taking at most one member from each pair allows at most five distinct selections.)* Division by a positive integer d gives d remainder categories: 0 through d-1. Equal remainders give a divisible difference. Write a = du+r and b = dv+r; then a-b = d(u-v), a multiple of d. Thus d+1 selected integers force two whose difference is divisible by d. The d integers 0 through d-1 have different remainders, showing that d selections need not suffice. The ceiling bound is sharp. Write m = qn+s, where q and s are integers and 0 <= s < n. Put q+1 objects in s boxes and q in the other n-s boxes. This places s(q+1)+(n-s)q = m objects. If s=0, every box holds q = ceiling(m/n). If s>0, the largest occupancy is q+1 = ceiling(m/n). No larger lower bound works for every placement. **Recap.** Assign each object to one category. Compare counts or capacities. A guarantee concerns every allowed placement, even when the proof does not identify the repeated objects. *Lesson, practice questions, worked solutions and flashcards written for this dataset.* ## Practice 18 questions on this page, each with its working shown. ## Needs first - [Proof by Contradiction and Counterexample](https://lightmysky.com/learn/mathematics/proof-by-contradiction-and-counterexample-mt_pbFTv4v6k8) ## Optional connections - [Binomial Coefficients and Combinatorial Identities](https://lightmysky.com/learn/mathematics/binomial-coefficients-and-combinatorial-identities-mt_lHXFvudTh6) ## Opens up - [Inclusion-Exclusion](https://lightmysky.com/learn/mathematics/inclusion-exclusion-mt_MgU-IMpVHA)