The pigeonhole principle: guaranteed coincidences in counting problems

What this dot point is asking

NESA wants you to recognise problems where the pigeonhole principle applies, identify the "boxes" and "pigeons" appropriately, and use the principle to prove that some box must contain at least two objects (or more, in the generalised form). The principle itself is almost trivially true; the marks are won by the modelling, that is, choosing the boxes so cleverly that "two pigeons in one box" turns into exactly the statement you were asked to prove.

The answer

The pigeonhole principle (basic form)

If $n + 1$ or more objects are placed into $n$ boxes, then at least one box contains at least $2$ objects.

Why: if every box held at most $1$ object, the total number of objects could be at most $n$, which contradicts having $n + 1$ or more. This is a proof by contradiction, and it is worth writing out that one line in an exam because it shows you understand why the principle holds, not just that it does.

Watch objects fill the boxes, stage by stage

The principle is easiest to believe when you try (and fail) to keep every box to one object. Take $4$ boxes and place objects one at a time. The first four can spread out, but the fifth has nowhere new to go.

Stage 1, place the first object. Drop object 1 into a box. Every box still holds at most one object, so there is no doubling-up yet.

Stage 2, fill every box once. Objects 2, 3 and 4 each take an empty box. Now all four boxes hold exactly one object. This is the tight case: with exactly as many objects as boxes, you can avoid a repeat, so $4$ objects in $4$ boxes guarantees nothing.

Stage 3, the fifth object forces a pair. Every box is already occupied, so the fifth object must share a box with one already there. Whichever box it lands in (box 1 shown) now holds two. This is the principle: $5 = 4 + 1$ objects in $4$ boxes forces a repeat.

The generalised pigeonhole principle

If $k n + 1$ or more objects are placed into $n$ boxes, then at least one box contains at least $k + 1$ objects.

The reasoning is the same contradiction: if every one of the $n$ boxes held at most $k$ objects, the total would be at most $kn$, contradicting $kn + 1$. Equivalently, if $m$ objects are placed in $n$ boxes, at least one box contains at least

objects (the ceiling, the smallest integer not less than $\frac{m}{n}$). The basic form is just $k = 1$.

Strategy for applying it

1. Identify the objects (pigeons) and the categories (boxes).
2. Count the number of each.
3. Check whether the pigeons exceed (or sufficiently exceed) the boxes, that is $m > n$ for the basic form, or $m > kn$ for the generalised form.
4. State the conclusion, naming the principle.

The whole difficulty, and where the marks are, is step 1: choosing the boxes so that two pigeons in one box gives the statement you want.

Common box choices

• Remainders modulo $n$. Any $n + 1$ integers must include two with the same remainder on division by $n$, so their difference is divisible by $n$. This is the most common HSC pattern.
• Intervals partitioning a range. Split a length or a range of values into equal sub-intervals; the values in the range are the pigeons. (The $25$-points-in-a-square question splits the square into $16$ cells.)
• Sums or subset-sums. When proving two subsets share a sum, the possible sums are the boxes and the subsets are the pigeons.
• Pairs that "use up" a value. When proving two of a collection match, the distinct possible values are the boxes.

Limitations

The pigeonhole principle gives existence, not construction. It tells you that two such objects exist, but never which ones. It is also sharp: with exactly $n$ objects in $n$ boxes, every box can hold exactly one, so $m = n$ guarantees nothing, you genuinely need $m \ge n + 1$. The same sharpness applies to the generalised form at $m = kn$.

How exam questions ask about the pigeonhole principle

• "Show that among any $N$ [integers / people / points] ... two must ...": a near-certain pigeonhole. Make the "..." the box description.
• "... two leave the same remainder on division by $d$" / "... two whose difference is divisible by $d$": boxes are the $d$ remainders $0, 1, \dots, d - 1$.
• "... two share a [birthday month / starting letter / value]": boxes are the categories (12 months, 26 letters, and so on).
• "Show that at least $k$ of them ...": the generalised form; you need more than $(k - 1) \times (\text{boxes})$ pigeons.
• Points in a region, "two within distance $d$": cut the region into cells whose diameter is $d$; the cells are the boxes.
• The phrasing is almost always "show that", "prove that", or "must" (a guarantee), never "find" or "how many" (those are direct counting). A guarantee with more objects than obvious categories is the cue.