What is off-by-one in the bound?

"n + 1 or more" pigeons forces a box with 2; exactly n pigeons does not. State the strict inequality.

What is generalised-form miscount?

kn + 1 pigeons force k + 1 in some box; kn pigeons do not. Use the ceiling m/n to be safe, and double-check whether m = kn exactly (in which case the guarantee is only k).

§-Syllabus dot point

NSWMaths Extension 1Syllabus dot point

When can we guarantee that some box contains more than one object, and how do we apply this to counting and existence arguments?

State and apply the pigeonhole principle in counting and existence problems

A focused answer to the HSC Maths Extension 1 dot point on the pigeonhole principle. The basic and generalised forms, identifying boxes and pigeons in a problem, and using the principle to prove existence statements, with a stepped objects-into-boxes diagram and worked examples.

Generated by Claude Opus 4.810 min answerUpdated 2026-06-20

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

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

\left\lceil \frac{m}{n} \right\rceil

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

Strategy for applying it

Identify the objects (pigeons) and the categories (boxes).
Count the number of each.
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.
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.

Worked example

Share a birthday month (basic form)

Show that among any $13$ people, at least two share a birthday month. The boxes are the $12$ months; the pigeons are the $13$ people. Since $13 = 12 + 1 > 12$ , by the pigeonhole principle at least one month is shared by two people.

Share a birth date (larger numbers, same idea)

Show that among any $367$ people, at least two share a birth date. The boxes are the $365$ possible dates (ignoring leap years); the pigeons are the $367$ people. Since $367 > 365$ , some date is shared by at least two people. (This is the certainty point of the birthday problem.)

Force five with the same remainder (generalised form)

Show that among any $25$ integers, at least $5$ leave the same remainder when divided by $6$ . The boxes are the $6$ remainders $0, \dots, 5$ ; the pigeons are the $25$ integers. Since $\left\lceil \frac{25}{6} \right\rceil = 5$ (equivalently $25 > 4 \times 6 = 24$ ), at least one remainder is shared by $5$ of the integers.

Find a difference divisible by four (choosing the boxes)

Show that among any $5$ integers, there are two whose difference is divisible by $4$ . Let the boxes be the $4$ remainders $0, 1, 2, 3$ modulo $4$ ; the $5$ integers are the pigeons. Since $5 > 4$ , two integers share a remainder. If $a$ and $b$ have the same remainder modulo $4$ , then $a - b$ is divisible by $4$ , which is the required conclusion.

Two close points in a square (geometry)

Show that if $5$ points are placed inside a $2 \times 2$ square, two of them are at most $\sqrt{2}$ apart. Cut the square into four $1 \times 1$ cells (the boxes). With $5$ points and $4$ cells, some cell contains at least two points. The farthest two points in a $1 \times 1$ cell are at its diagonal, $\sqrt{1^2 + 1^2} = \sqrt{2}$ , so those two points are at most $\sqrt{2}$ apart.

Two subsets with equal sums (subset-sum)

Show that any $10$ distinct two-digit numbers contain two different subsets with the same sum. There are $2^{10} - 1 = 1023$ non-empty subsets (the pigeons). Each subset sum lies between $10$ (the smallest possible single element) and $90 + 91 + \dots + 99 = 945$ (the largest possible total), so there are at most $945 - 10 + 1 = 936$ possible sums (the boxes). Since $1023 > 936$ , two different subsets share a sum. Removing any common elements from both leaves two disjoint subsets with equal sums.

Common traps

Wrong choice of boxes: The principle only helps if "two pigeons in one box" gives the conclusion you want. Choosing boxes carelessly proves nothing. This is where most marks are lost.
Off-by-one in the bound: " $n + 1$ or more" pigeons forces a box with $\ge 2$ ; exactly $n$ pigeons does not. State the strict inequality.
Generalised-form miscount: $kn + 1$ pigeons force $\ge k + 1$ in some box; $kn$ pigeons do not. Use the ceiling $\lceil m/n \rceil$ to be safe, and double-check whether $m = kn$ exactly (in which case the guarantee is only $k$ ).
Trying to construct: The principle is existence-only. Do not attempt to say which box has the extras or which objects coincide.
Confusing it with exact counting: Pigeonhole proves "at least one box has $\ge k$ "; it never says how many boxes do, nor exactly how full any box is.

Exam-style practice questions

Practice questions written in the style of NESA exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

HSC-style2 marksShow that among any

5

integers, at least two leave the same remainder when divided by

4

Show worked answer →

When an integer is divided by $4$ , the possible remainders are $0, 1, 2, 3$ , which is $4$ categories (boxes).

The $5$ integers are the pigeons. Since $5 > 4$ , by the pigeonhole principle at least one remainder is shared by two of the integers.

Hence at least two of the five integers have the same remainder modulo $4$ .

HSC-style3 marks

25

points are placed inside a square of side length

1

. Show that some pair of points is at most

\frac{\sqrt{2}}{4}

apart.

Show worked answer →

Divide the unit square into a $4 \times 4$ grid of $16$ smaller squares, each of side $\frac{1}{4}$ (these are the boxes).

There are $25$ points (pigeons) and $16$ small squares. Since $25 > 16$ , by the pigeonhole principle at least one small square contains at least two of the points.

The greatest distance between two points within a small square is its diagonal, $\sqrt{\left( \tfrac{1}{4} \right)^2 + \left( \tfrac{1}{4} \right)^2} = \frac{\sqrt{2}}{4}$ .

Therefore those two points are at most $\frac{\sqrt{2}}{4}$ apart.