Pigeonhole principle
The pigeonhole principle: simple and generalized statements, proofs, formulas and exam-style worked examples showing how to guarantee collisions or minimum occupancy when objects are placed into boxes.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Two or three sentences: Engineers use the pigeonhole principle to prove that some resource will be shared, collide, or overflow when capacity is limited. Examples: proving that a hash table bucket must contain at least two keys when there are more keys than buckets, or guaranteeing minimum load per server when tasks exceed servers.
Key ideas
Start from first principles and define terms before using them.
Pigeonhole principle (basic form): If N objects (called pigeons) are placed into k containers (called holes or boxes) and N > k, then at least one box contains at least two pigeons. Assumption: each pigeon is assigned to exactly one box.
Generalized pigeonhole principle (also called Dirichlet's box principle): If N objects are placed into k boxes, then at least one box contains at least (\lceil N/k\rceil) objects. Assumption: each object goes to exactly one box; k ≥ 1.
Strong form (equivalent statement): For integers N, k, m with k ≥ 1, if N > (m − 1)·k then some box contains at least m objects. This is the same as saying if we want at least m objects in some box, we must have N > (m−1)k. Equivalently, N ≥ (m − 1)·k + 1. Equivalent function form: If f: A → B with finite sets and |A| > |B|, then f is not injective; some distinct a1, a2 ∈ A have f(a1) = f(a2).
Ceiling function: Ceiling of a real x, written (\lceil x\rceil), is the smallest integer ≥ x. We use it to express the exact minimum guaranteed occupancy.
Proofs universities expect (step-by-step):
Basic form (proof by contradiction):
- Assume N > k and yet every box has at most one pigeon.
- Then total pigeons ≤ k (because each of k boxes has 0 or 1 pigeon).
- This contradicts N > k. Therefore some box has at least two pigeons.
Generalized form (proof using contradiction or division):
- Suppose every box has at most (\lceil N/k\rceil - 1) pigeons.
- Then total pigeons ≤ k·((\lceil N/k\rceil - 1)). But k·((\lceil N/k\rceil - 1)) < k·(N/k) = N, a contradiction.
- Equivalent simpler proof: write N = q·k + r with integers q ≥ 0 and 0 ≤ r < k (division algorithm). Then q = (\lfloor N/k\rfloor) and r = N mod k. Distribute q pigeons to each box, remaining r pigeons go one each to r boxes. So r boxes have q+1 pigeons and others have q. Hence some box has q+1 = (\lceil N/k\rceil) pigeons.
Strong form: Solve (\lceil N/k\rceil ≥ m) for N. This is equivalent to N > (m−1)k. Provide proof by rewriting.
Diagram to draw (if exam asks): Draw k labeled boxes in a row: Box 1, Box 2, ..., Box k. Inside each box draw small dots to represent pigeons. For the division argument, draw q dots in each box and then put one extra dot in r leftmost boxes (label r). Also draw a small caption: N = q·k + r.
Notes on assumptions and limits: The principle is a counting existence result only — it guarantees existence of at least one box with the claimed occupancy but does not identify which box without further information.
Formulas
If N objects and k boxes then some box has at least ceil(N/k) objects. — N: number of objects (unitless), k: number of boxes (unitless). Applies for integers N ≥ 0, k ≥ 1.
If N > (m - 1)·k then some box contains at least m objects. — N, k, m integers; unitless. Applies for k ≥ 1 and m ≥ 1.
N = q·k + r, where q = floor(N/k), 0 ≤ r < k — q and r integers; unitless. This is the division algorithm used in the constructive proof.
ceil(x) = smallest integer ≥ x — defines ceiling; unitless. Applies to any real x.
(These expressions are combinatorial; there are no SI units — quantities are unitless counts.)
Worked examples
Example 1 — months and people (short exam-style): Question: Show that in any group of 13 people at least two were born in the same month. Solution steps:
- Pigeons: 13 people. Holes: k = 12 months.
- Use generalized principle: some month has at least ceil(13/12) people.
- Compute ceil(13/12) = ceil(1.0833...) = 2.
- Therefore at least two people share a birth month. Final answer: 2 people.
Example 2 — socks in a drawer (typical minimal-number problem): Question: A drawer contains 6 black socks and 4 white socks. How many socks must you take at random (in the dark) to guarantee you have at least one pair of the same colour? Solution steps:
- Pigeons: socks you pick. Boxes: two colours (k = 2).
- By the basic pigeonhole principle, to force two items in the same box you need k+1 picks.
- So you must pick 2 + 1 = 3 socks.
- Final answer: 3 socks (worst case: first pick black, second pick white, third must match one colour already chosen).
Example 3 — residues modulo n (longer): Question: From the integers 1 to 200, if you choose 101 distinct integers, show that two chosen integers give the same remainder when divided by 100. Solution steps:
- Pigeons: 101 chosen integers. Boxes: possible remainders modulo 100, which are 0,1,2,...,99; so k = 100 boxes.
- Apply generalized principle: some remainder class has at least ceil(101/100) = 2 elements.
- Therefore there exist two chosen integers with the same remainder modulo 100. Final answer: Yes — at least two share a remainder.
Example 4 — minimum births per month (numerical): Question: If 500 students are in a college, show that some month has at least how many birthdays? Solution steps:
- N = 500, k = 12.
- ceil(500/12) = ceil(41.666...) = 42.
- So at least 42 students share a birth month.
Common mistakes
- Forgetting to check k ≥ 1 and integer assumptions when applying formulas.
- Miscounting holes (e.g., months = 12 but forgetting February special-case is irrelevant because months are boxes; day-count details do not affect pigeonhole count).
- Assuming the principle identifies which box — it only guarantees existence.
For your exam
Kinds of questions and what full-marks answers include:
- Definition question: State and prove the pigeonhole principle (basic and generalized). Full marks: clear definitions of pigeons and holes, exact statement with ceiling, and a correct proof (contradiction or division algorithm).
- Short note: Give applications in computing (hashing collisions, load balancing). Full marks: short examples and explanation linking counts to boxes.
- Derivation problem: Prove the strong form: N > (m−1)k implies some box has ≥ m objects. Full marks: algebraic manipulation and logical steps, or equivalently use ceiling formula.
- Numerical problems: Compute the minimum guaranteed number in a box for given N, k. Full marks: show formula used, compute ceil(N/k) with intermediate decimal and final integer.
- Construction: Draw boxes and distribute q and r dots to show the division proof. Full marks: correct drawing as described in Key ideas and explanation of q and r.
Advice: Always state what are pigeons and holes in the problem, compute N and k explicitly, then apply the formula and give the numeric ceiling.
Quick check
- If 25 students are in a class and there are 12 months, what is the minimum number of students who share some month?
- If socks of 3 colours are in a drawer (assume unlimited supply per colour), how many socks must you take to guarantee at least 25 of the same colour?
- Prove briefly: if 10 integers are chosen, two will have difference divisible by 9. Answers: 1) ceil(25/12) = 3. 2) You need (m−1)·k + 1 = (25−1)·3 + 1 = 73; since 73 picks guarantee 25 of a colour, minimal required is 73. 3) Remainders modulo 9 are 0..8 (k=9), with 10 pigeons so some remainder class has at least ceil(10/9)=2, therefore two integers have equal remainder mod 9, so their difference is divisible by 9.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?