The Pigeonhole Principle: HSC Mathematics Extension 1

Thirty-one students are spread across the twelve months of the year according to their birth months. Can you prove that at least three students were born in the same month, without knowing a single birthday?

Yes. Imagine trying to avoid having three students in any month. You could put two students in January, two in February, and so on. But even if every month contained exactly two students, you would only have accounted for 24 students. The remaining seven students have to go somewhere, so at least one month must contain three or more.

This simple argument is an example of the pigeonhole principle. It lets you prove that something must happen, even when you have no information about the exact arrangement of objects.

01The pigeonhole principle

The basic pigeonhole principle states:

If more than \(n\) objects are distributed among \(n\) boxes, at least one box must contain two or more objects.

The name comes from the idea of putting pigeons into pigeonholes. If you have more pigeons than holes, you cannot give every pigeon its own hole.

The important part is that you don’t need to know how the objects are distributed. You only need to know how many objects and boxes there are.

For example:

• 13 students distributed across 12 birth months guarantees that at least two share a birth month.
• 21 integers distributed across 20 possible remainders guarantees that at least two have the same remainder when divided by 20.
• 6 objects distributed across 5 containers guarantees that at least one container holds two or more objects.

Why does it work?

Suppose you have 8 boxes and 9 objects.

Could every box contain at most one object?

No. If that were possible, you could fit only 8 objects. The ninth object would have nowhere to go without sharing a box.

That’s the entire proof.

More formally, suppose \(n+1\) objects are distributed among \(n\) boxes. If every box contained at most one object, the total number of objects could not exceed \(n\).

But there are \(n+1\) objects.

This is a contradiction, so at least one box must contain two or more objects.

The argument is short, but the real skill in an exam question is usually deciding what the boxes should represent.

02The generalised pigeonhole principle

The basic principle guarantees at least two objects in one box. We can go further and guarantee three, four, or even more.

Suppose \(N\) objects are distributed among \(k\) boxes.

The generalised pigeonhole principle states that at least one box must contain at least

\[ \boxed{\left\lceil\frac{N}{k}\right\rceil} \]

objects.

The symbol \(\lceil x\rceil\) means the ceiling of \(x\): the smallest integer greater than or equal to \(x\).

For example, if 11 objects are distributed among 4 boxes,

\[ \left\lceil\frac{11}{4}\right\rceil = \lceil 2.75\rceil =3 \]

Therefore, at least one box must contain three or more objects.

Why? If every box contained at most two objects, the maximum total would be

\[ 4\times 2=8 \]

But we have 11 objects. At least one box must contain three.

A useful alternative formula

Sometimes an exam question asks how many objects are needed to guarantee a particular number in one box.

Suppose you want to guarantee at least \(r\) objects in one of \(k\) boxes.

The maximum number of objects you could distribute without reaching \(r\) in any box is

\[ k(r-1) \]

Each box can contain at most \(r-1\) objects without meeting the target.

Therefore, adding just one more object forces at least one box to contain \(r\) objects.

The required number is

\[ \boxed{N=k(r-1)+1} \]

This gives three particularly useful results:

Return to the 12 birth months.

To guarantee at least three students share a birth month, you need

\[ N=12(3-1)+1 \]

\[ \boxed{N=25} \]

So 25 students are enough. Our original group of 31 students gives an even stronger guarantee.

Notice that 24 students would not be enough: you could have exactly two students born in each month.

This distinction is important. The principle gives a guarantee, and the threshold formula tells you exactly when that guarantee first becomes unavoidable.

03The real challenge: choosing the boxes

In examination questions, the boxes are rarely given to you.

You need to invent a useful way of grouping the objects so that two objects sharing a box automatically satisfy the condition you want to prove.

Consider some common situations.

The key test is simple:

If two objects land in the same box, does that automatically give me the result I want?

If the answer is no, you probably need a different way of grouping them.

Using remainders as boxes

Remainders are particularly useful in pigeonhole problems.

When an integer is divided by 7, its remainder must be one of

\[ 0,1,2,3,4,5,6 \]

There are exactly seven possible remainders, so we can create seven boxes.

Now suppose two integers leave the same remainder when divided by 7.

We can write them as

\[ a=7p+r \]

and

\[ b=7q+r \]

where \(p\) and \(q\) are integers, and \(r\) is their shared remainder.

Subtracting gives

\[ a-b=7p-7q \]

\[ a-b=7(p-q) \]

Since \(p-q\) is an integer, the difference is divisible by 7.

This gives us an important result:

Two integers with the same remainder when divided by \(m\) have a difference divisible by \(m\).

We can express this using modular notation:

\[ a\equiv b\pmod m \]

This means that \(a\) and \(b\) have the same remainder when divided by \(m\).

04Common mistakes to avoid

There are a few traps worth recognising before attempting examination questions.

1. Confusing the average with the guaranteed minimum

If 30 objects are distributed among 7 boxes, the average occupancy is

\[ \frac{30}{7}\approx4.29 \]

You cannot have 4.29 objects in a box. The guarantee is therefore at least 5 objects in one box.

Always round the average upwards using the ceiling function.

2. Assuming the distribution must be even

The pigeonhole principle does not say that objects are distributed equally.

For example, 13 objects in 4 boxes guarantees at least 4 objects in one box. It does not mean the distribution must be 4, 3, 3, 3.

A distribution such as 7, 2, 2, 2 is also possible.

3. Choosing boxes that don’t establish the required property

If a question asks you to prove that two integers have a difference divisible by 6, grouping them according to whether they are positive or negative won’t help.

You need six remainder classes, because sharing a remainder guarantees the required divisibility.

4. Forgetting to explain why sharing a box matters

Writing “there are 11 objects and 10 boxes, so two must share a box” is only part of a proof.

You must also explain what sharing that particular box tells you about the original objects.

In an HSC-style proof, the connection between the grouping and the required conclusion is essential.

05Questions and solutions

The following questions move from straightforward applications towards problems where the most important step is finding a less obvious set of boxes.

Question 1

A school distributes 73 Year 12 students among 8 mathematics tutorial groups.

What is the smallest number of students that you can guarantee will be in at least one group? Prove your answer.

Solution 1

At least one group must contain 10 or more students.

There are 73 students and 8 groups.

Using the generalised pigeonhole principle,

\[ \begin{aligned} N&=73\\ k&=8 \end{aligned} \]

The minimum guaranteed number is

\[ \left\lceil\frac{73}{8}\right\rceil = \lceil9.125\rceil \]

\[ \boxed{10\text{ students}} \]

We can also prove this using contradiction.

Suppose every group contained at most 9 students.

The maximum total number of students would then be

\[ 8\times9=72 \]

But there are 73 students.

This is impossible, so at least one group must contain 10 or more students.

The answer is the smallest guaranteed number, not necessarily the exact size of the largest group. Several groups could contain 10 or more students.

Question 2

Six people attend a gathering.

Each person counts how many of the other five people they are friends with. Assume friendship is mutual: if person A is friends with person B, then person B is friends with person A.

Prove that at least two people must have the same number of friends within the group.

Solution 2

At least two people must have the same number of friends.

The key is to recognise that although there appear to be six possible friend counts, from 0 to 5, not all six counts can occur simultaneously.

Step 1: Identify the possible friend counts.

Each person can have anywhere from zero to five friends.

Initially, this gives six possible values:

\[ 0,1,2,3,4,5 \]

However, there is an important restriction.

Step 2: Identify the impossible combination.

Can one person have zero friends while another has five?

No.

If someone has five friends, they must be friends with everyone else in the group.

That includes the person who supposedly has zero friends.

Since friendship is mutual, these two situations cannot occur together.

Therefore, at least one of the values 0 and 5 must be absent.

Step 3: Count the remaining boxes.

If someone has zero friends, nobody can have five. The possible counts are then

\[ 0,1,2,3,4 \]

Alternatively, if nobody has zero friends, the possible counts are

\[ 1,2,3,4,5 \]

Either way, there are at most five possible friend counts.

Step 4: Apply the pigeonhole principle.

We have six people and at most five possible friend counts.

Therefore, at least two people must have the same number of friends.

The subtlety here is that you cannot simply count six possible values and conclude that a repeat must occur. You first need to recognise that the two extreme values cannot coexist.

This is a useful technique in harder pigeonhole questions: investigate whether some apparently possible boxes are actually incompatible.

Question 3

Five integers are selected.

Prove that there must be three of these integers whose sum is divisible by 3.

Also, show that four integers are not sufficient to guarantee this result.

Solution 3

There must be three integers whose sum is divisible by 3, and four integers are not enough to guarantee this.

The proof depends on considering two possible arrangements of the five integers according to their remainders.

Step 1: Identify the remainder classes.

Every integer has one of three possible remainders when divided by 3:

\[ 0,\quad 1,\quad 2 \]

These are our three boxes.

Step 2: Consider the first possibility.

Suppose at least three integers have the same remainder.

If their common remainder is \(r\), where \(r\) is 0, 1, or 2, the sum of the three integers has remainder

\[ r+r+r=3r \]

Since \(3r\) is divisible by 3, the sum of these three integers must be divisible by 3.

We have proved the result in this case.

Step 3: Consider the alternative.

What if no remainder occurs three times?

Each of the three boxes can contain at most two integers.

We have five integers in total, so the only possible distribution is

\[ 2,\quad 2,\quad 1 \]

This means that every remainder class must contain at least one integer.

Choose one integer from each class.

Their remainders are 0, 1, and 2, so their sum has remainder

\[ 0+1+2=3 \]

Therefore, their sum is divisible by 3.

This completes the proof.

Step 4: Show that four integers are insufficient.

Consider the four distinct integers

\[ 0,\quad 3,\quad 1,\quad 4 \]

Their possible three-integer sums are

\[ \begin{aligned} 0+3+1&=4\\ 0+3+4&=7\\ 0+1+4&=5\\ 3+1+4&=8 \end{aligned} \]

None of these sums is divisible by 3.

Therefore, four integers do not guarantee the required result.

The important idea is that failing to find three integers in the same remainder class doesn’t mean the proof has failed. The remaining distribution forces all three remainder classes to be represented, which gives us a different way to construct the required triple.

Question 4

Five distinct points are placed anywhere inside a square with side length 1.

Prove that at least two of the points must be separated by a distance no greater than

\[ \frac{1}{\sqrt{2}} \]

Show that this bound is the best possible: that is, demonstrate that no smaller universal upper bound can be guaranteed.

Solution 4

At least two points must be separated by a distance of at most

\[ \boxed{\frac{1}{\sqrt{2}}} \]

Furthermore, this bound is exact.

Step 1: Divide the square into four smaller squares.

Draw one vertical line and one horizontal line through the midpoints of the original square’s sides.

This creates four smaller squares, each with side length

\[ \frac{1}{2} \]

Treat these four smaller squares as our four boxes.

Assign any points lying on dividing lines consistently to one of the adjacent regions.

Step 2: Apply the pigeonhole principle.

We have five points distributed among four smaller squares.

Therefore, at least one smaller square must contain two or more points.

Choose any two points in that smaller square.

Step 3: Find the maximum possible distance between those points.

The greatest possible separation occurs when the points lie at opposite corners of the smaller square.

The smaller square has side length \(1/2\).

Using Pythagoras’ theorem, its diagonal is

\[ d^2= \left(\frac12\right)^2+ \left(\frac12\right)^2 \]

\[ d^2=\frac14+\frac14 \]

\[ d^2=\frac12 \]

Therefore,

\[ d=\sqrt{\frac12} =\frac{1}{\sqrt2} \]

Since both points lie inside the same smaller square, their distance cannot exceed this diagonal.

Hence,

\[ \boxed{d\leq\frac{1}{\sqrt2}} \]

Step 4: Show that the bound cannot be improved.

Consider placing four points at the four corners of the original unit square and the fifth point at its centre.

The distance from the centre to any corner is

\[ d=\sqrt{ \left(\frac12\right)^2+ \left(\frac12\right)^2 } \]

\[ d=\frac{1}{\sqrt2} \]

The distances between adjacent corners are 1, and between opposite corners are \(\sqrt2\).

Therefore, the smallest distance between any pair of these five points is exactly

\[ \frac{1}{\sqrt2} \]

So no smaller universal upper bound is possible.

Notice the two separate jobs in this proof.

The pigeonhole principle guarantees that two points occupy the same smaller square. Pythagoras’ theorem then converts that shared location into a numerical distance bound.

This is a powerful combination: use pigeonhole reasoning to establish where two objects must be, then use geometry to establish how far apart they can be.

Question 5

Six integers are written in a row:

\[ a_1,a_2,a_3,a_4,a_5,a_6 \]

Prove that there must be at least one non-empty consecutive block of these integers whose sum is divisible by 6.

A consecutive block consists of one or more adjacent entries. For example, \(a_2+a_3+a_4\) is a consecutive block, but \(a_1+a_3+a_5\) is not.

Also, show that six is the smallest number of integers that guarantees this result.

Solution 5

There must be a non-empty consecutive block whose sum is divisible by 6. Six integers are the minimum needed to guarantee this for an arbitrary sequence.

The clever step is not to put the original six integers into remainder boxes. Instead, we examine their cumulative sums.

Step 1: Construct the partial sums.

Define the partial sums as

\[ \begin{aligned} S_1&=a_1\\ S_2&=a_1+a_2\\ S_3&=a_1+a_2+a_3\\ &\ \vdots\\ S_6&=a_1+a_2+a_3+a_4+a_5+a_6 \end{aligned} \]

Each partial sum represents the total of all entries from the beginning of the sequence up to a particular position.

We now have six partial sums.

Step 2: Consider their possible remainders when divided by 6.

There are six possible remainders:

\[ 0,1,2,3,4,5 \]

We consider two cases.

Case 1: At least one partial sum has remainder zero.

Suppose \(S_k\) is divisible by 6.

By definition,

\[ S_k=a_1+a_2+\cdots+a_k \]

This is a non-empty consecutive block consisting of the first \(k\) integers.

Its sum is divisible by 6, so the required result is established.

Case 2: None of the six partial sums has remainder zero.

Now comes the important observation.

If none of the partial sums is divisible by 6, their possible remainders are restricted to

\[ 1,2,3,4,5 \]

There are only five possible remainders.

But we have six partial sums:

\[ S_1,S_2,S_3,S_4,S_5,S_6 \]

By the pigeonhole principle, at least two partial sums must have the same remainder.

Suppose these are \(S_i\) and \(S_j\), where \(i<j\).

Their difference must be divisible by 6.

Step 3: Connect the repeated remainder to a consecutive block.

Consider

\[ S_j-S_i \]

Expanding both partial sums gives

\[ \begin{aligned} S_j-S_i ={}&(a_1+\cdots+a_i\\ &+a_{i+1}+\cdots+a_j)\\ &-(a_1+\cdots+a_i) \end{aligned} \]

All the common terms cancel, leaving

\[ S_j-S_i = a_{i+1}+a_{i+2}+\cdots+a_j \]

This is a consecutive block of the original sequence.

Since \(S_i\) and \(S_j\) have the same remainder when divided by 6, their difference is divisible by 6.

Therefore, this non-empty consecutive block has a sum divisible by 6.

Both cases produce the required result, so the theorem is proved.

Step 4: Prove that six is the minimum required.

Consider a sequence of five positive integers:

\[ 1,1,1,1,1 \]

Every non-empty consecutive block consists of between one and five entries.

Its sum must therefore be one of

\[ 1,2,3,4,5 \]

None of these sums is divisible by 6.

So five integers do not guarantee the result.

Since six integers always work, but five do not, the minimum required number is

\[ \boxed{6} \]

The tempting approach would be to place the six original integers into six remainder classes. That gives no guaranteed repetition, because the number of integers and the number of possible remainders are equal.

The breakthrough is to change the objects being grouped.

By examining partial sums, we create a situation where either:

• A partial sum is already divisible by 6, giving us the required block immediately; or
• All six partial sums must fit into just five non-zero remainder classes, forcing two to share a remainder.

That second possibility is what makes the proof work. The zero remainder isn’t simply another box: if it occurs, the problem is already solved.

06What to look for in your next proof

The pigeonhole principle is most useful when you stop thinking about the physical objects and start thinking about the mathematical property you want to force.

When you encounter an unfamiliar question, make three decisions:

• What are my objects? These might be integers, points, people, or partial sums.
• What are my boxes? These might be remainder classes, complementary pairs, geometric regions, or possible numerical values.
• What does sharing a box prove? This is the connection that turns the counting argument into a mathematical proof.

In more demanding problems, the objects and boxes may not be obvious at all. The partial-sums question is a good example: the original integers were not the right objects to group.

Once you become comfortable choosing the boxes, the next natural step is combining pigeonhole arguments with modular arithmetic, sequences, and geometric inequalities. That’s where a simple counting principle can produce some surprisingly powerful proofs.