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 worked examples.

Generated by Claude OpusReviewed by Better Tuition Academy6 min answerUpdated 2026-05-20

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 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 contained at most $1$ object, the total would be at most $n$ , contradicting that there are $n + 1$ or more.

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.

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).

Strategy for applying it

Identify the objects (pigeons) and the categories (boxes).
Count the number of each.
Check whether pigeons exceed (or sufficiently exceed) the boxes.
Conclude the required statement.

Often the trick is in cleverly choosing the boxes.

Common box choices

Remainders modulo $n$ . $n + 1$ integers must include two with the same remainder.
Subsets or "buckets" of values. Partition a range into intervals; values in the range are pigeons.
Sums of subsets. When proving two subsets have the same sum, the sums are pigeons.
Pairs of values. When proving two of a collection match, the values are pigeons.

Limitations

The pigeonhole principle gives existence, not construction. You learn that two such objects exist, but not which ones.

The principle is sharp: with exactly $n$ objects in $n$ boxes, every box can have exactly $1$ , so no guarantee of doubling-up.

Worked example

Basic application

Among any group of $13$ people, at least two share a birthday month.

There are $12$ months (boxes) and $13$ people (pigeons). $13 = 12 + 1$ , so the basic pigeonhole principle gives the result.

With moderate numbers

Among any $367$ people, at least two share a birth date.

$365$ possible dates (boxes), $367$ pigeons. By pigeonhole, at least one date has $\ge 2$ people. (This is the resolution of the birthday paradox at sample size $367$ .)

Generalised form

Among any $25$ integers, at least $5$ have the same remainder when divided by $6$ .

$6$ boxes (remainders), $25$ pigeons. $\left\lceil \frac{25}{6} \right\rceil = 5$ , so at least one box has $\ge 5$ .

Choosing boxes cleverly

Show that among any $5$ integers, there must be two whose difference is divisible by $4$ .

Boxes: the $4$ possible remainders modulo $4$ ( $0, 1, 2, 3$ ). Pigeons: the $5$ integers. By pigeonhole, two of the integers have the same remainder, so their difference is divisible by $4$ .

Sum identical

Show that among any $7$ distinct integers from $1$ to $12$ , there are two whose difference is exactly $3$ or whose sum is exactly $15$ .

A more subtle problem. Pair up integers: $\{1, 4\}, \{2, 5\}, \{3, 6\}$ (differ by 3); $\{4, 11\}, \{5, 10\}, \{6, 9\}, \{7, 8\}$ etc. Form groups of size 2 or 3 such that any two members satisfy the difference or sum condition. With $7$ integers and (cleverly chosen) $6$ groups, two integers share a group.

Detailed pairing (this requires reading; setting up the groups is the tricky part of pigeonhole problems).

Two values matching

Show that among any $11$ digits chosen from $0$ to $9$ , two must be equal.

$10$ digits available (boxes), $11$ chosen. By pigeonhole, at least one digit is chosen twice.

Sums of subsets

Show that any set of $10$ distinct two-digit numbers contains two disjoint subsets with the same sum.

There are $2^{10} - 2 = 1022$ non-empty proper subsets. The maximum sum is $10 \cdot 99 = 990$ , but the actual maximum for any $10$ distinct two-digit numbers is at most $90 + 91 + \dots + 99 = 945$ .

Each subset has a sum between $10$ (the smallest single number) and $945$ . So sums fall into at most $945 - 10 + 1 = 936$ values.

By pigeonhole, two distinct subsets share a sum. Remove their intersection from both, and you get two disjoint subsets with the same sum.