The pigeonhole principle
If n objects go into m boxes with n > m, some box holds at least two — obvious, yet the source of surprisingly deep results. The generalised form says some box holds at least ⌈n/m⌉. The difficulty is never the principle; it is choosing what to call the pigeons and what to call the holes, and that choice is where the marks are.
✓ Unlimited questions · marked criterion by criterion · no card needed
Method: how to approach it
The order below is what examiners expect to see, and each step carries its own marks.
- Identify the pigeonsThe objects being placed — usually the things the question says "any n of".
- Identify the holesThe categories. Often these must be constructed: residues mod n, intervals, or pairs summing to a target.
- Compare the countsShow pigeons exceed holes, or apply ⌈n/m⌉ for the stronger conclusion.
- State the conclusion explicitlyTwo pigeons share a hole — then translate back into the language of the problem.
Worked example
Show that among any 5 integers, two have the same remainder on division by 4.
- Pigeons: the 5 integers.
- Holes: the possible remainders 0, 1, 2, 3 — four of them.
- 5 > 4, so by the pigeonhole principle two integers share a remainder.
- Equivalently, their difference is divisible by 4.
Answer. Two of any five integers are congruent mod 4, so their difference is a multiple of 4.
Where marks get dropped
These are the specific errors that cost credit on the pigeonhole principle questions — QED's rubric penalises each of them separately.
- Failing to construct the holes. Many problems need you to invent the categories — pairs summing to 9, or intervals of length 1/n.
- Using ⌊n/m⌋ in the generalised form. The bound is the CEILING.
- Claiming which box is full. Pigeonhole is purely existential — it never identifies the box.
Practise this until it is automatic
Unlimited fresh questions
QED generates new the pigeonhole principle problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.
Marked like an examiner
Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.
Answer in real notation
A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.
Saved to your library
Every question you generate is kept and re-takeable as a timed exam, and your Combinatorics mastery is tracked so you know when this is exam-ready.
The pigeonhole principle — frequently asked questions
What is the generalised pigeonhole principle?
With n objects in m boxes, some box holds at least ⌈n/m⌉. For 10 objects in 3 boxes, some box holds at least 4.
Give a classic non-obvious application.
Among any n+1 numbers chosen from 1…2n, two must be consecutive, hence coprime. The holes are the n pairs {1,2}, {3,4}, ….
Is there an infinite version?
Yes: partitioning an infinite set into finitely many classes leaves at least one class infinite. It is the base case of Ramsey theory.
The rest of Combinatorics
Counting principles, permutations, combinations. Each subtopic below has its own method, worked example and mark-losing traps.
- 1Sum & product rules
- 2Permutations & combinations
- 3Binomial theorem & Pascal’s triangle
- 4The pigeonhole principle
- 5Inclusion–exclusion
- 6Counting with repetition (stars & bars)
- 7Derangements & counting surjections
- 8Double counting & bijective proofs
- 9Setting up & solving counting recurrences
- 10Generating functions — an introduction
- 11Multinomial coefficients & repeated items
- 12Hockey stick & Vandermonde identities
- 13Catalan numbers & lattice-path counting
Ready to make the pigeonhole principle exam-proof?
Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.
Start practising free →