The pigeonhole principle and combinatorial proofs

On this page

Two counting ideas prove results that would otherwise need long case-by-case work. The pigeonhole principle says that if more objects than boxes are placed in boxes, some box holds at least two; the art is choosing the boxes. Double counting proves an identity by counting the same set in two different ways. This lesson applies both, writing each proof so that the objects, the boxes or the set being counted are stated explicitly.

The pigeonhole principle

If more than n objects are placed in n boxes, some box contains at least two objects. Otherwise each box has at most one, and there are at most n objects. More generally, if more than kn objects are placed in n boxes, some box contains at least k + 1.

The principle proves that something exists without saying where. The skill is in choosing the boxes: they must be defined so that any two objects in the same box have the property you want.

Five points are placed inside or on a square of side 2. Prove that two of them are at most square root of 2 apart.

Show full solutionHide solution

Choose the boxes
Method
Divide the square into four 1 × 1 squares.
Reason
Two points in the same small square are at most its diagonal, square root of 2, apart.
Working
Answer
Points on a shared edge can be assigned to either neighbouring square; every point is in at least one small square.
Apply the principle
Method
Five points, four boxes.
Reason
5 > 4, so some box holds two points.
Working
Answer
Those two points lie in one 1 × 1 square, so they are at most square root of 2 apart. blacksquare

Quick check

The bound is sharp: four corners and the centre of the big square give every pair at least square root of 2 apart. Four points would not be enough, since the four corners are 2 apart.

Let n be a positive integer. Prove that any n + 1 distinct integers chosen from {1,2,…,2n} include two that have no common factor greater than 1. [4]

Write your answer, then compare it with the solution

Your proof

Show full solutionHide solution

Define the boxes
Method
Use the n pairs {1,2},{3,4},…,{2n-1,2n}.
Reason
Every chosen integer belongs to exactly one pair.
Working
Answer
n + 1 chosen integers in n pairs: by the pigeonhole principle, some pair contains two chosen integers, k and k + 1.
Show consecutive integers are coprime
Method
Suppose d divides both k and k + 1.
Reason
Then d divides their difference.
Working
Answer
d divides (k + 1)-k = 1, so d = 1. Hence k and k + 1 have no common factor greater than 1. blacksquare

Self-mark with the mark scheme

Tick each mark point that your answer includes.

Tick a point only if your written proof contains it. This self-check does not record a mark.

Mark points

1 mark: Defines n boxes, the pairs {2j − 1, 2j}, covering every integer from 1 to 2n.
1 mark: States that n + 1 objects in n boxes force two chosen integers into one pair.
1 mark: Identifies those two as consecutive integers k and k + 1.
1 mark: Proves consecutive integers are coprime: a common divisor divides their difference, 1.

Common mistake

Saying “the two numbers are consecutive, so they are coprime” without a reason leaves the last mark unearned. The bound n + 1 is sharp: the n even numbers 2,4,…,2n share the factor 2.

Count the same set in two ways

A combinatorial proof shows two expressions are equal by showing they count the same set. It explains why an identity holds, often more clearly than algebra.

(n choose r) = (n choose (n-r)): choosing the r members of a committee from n people is the same as choosing the n-r people left out. This bijection pairs each choice with its complement.
(n choose r) = ((n-1) choose (r-1)) + ((n-1) choose r) for 1 ≤ r ≤ n-1: fix one person, Ann. Committees of r either include Ann (choose the other r-1 from n-1) or do not (choose all r from n-1). The two cases do not overlap and cover every committee.

A complete combinatorial proof names the set, explains each count, and says why the cases neither overlap nor miss anything.

Prove that ∑ᵣ₌₁ⁿr(n choose r) = n 2ⁿ⁻¹ by counting, in two ways, the ways to choose a committee of any size from n people, with one committee member as chair.

Your two counts and the conclusion

Show answerHide answer

Committee first. Choose a committee of size r ≥ 1 in (n choose r) ways, then its chair in r ways. Adding over r gives ∑ᵣ₌₁ⁿr(n choose r).

Chair first. Choose the chair in n ways. Each of the other n-1 people is either on the committee or not, giving 2ⁿ⁻¹ ways. That is n 2ⁿ⁻¹.

Both count the same set of (committee, chair) choices, so they are equal. Check with n = 7: both sides equal 448.

By considering the ways to choose n people from a group of n adults and n children, prove that

∑ᵣ₌₀ⁿ(n choose r)² = (2n choose n). [4]

Write your answer, then compare it with the solution

Your combinatorial proof

Show full solutionHide solution

Count directly
Method
Choose n people from all 2n.
Reason
This is the right-hand side.
Working
Answer
There are (2n choose n) ways.
Count by the number of adults
Method
Suppose the selection contains exactly r adults, so n-r children.
Reason
Each selection has exactly one value of r from 0 to n, so the cases neither overlap nor miss any selection.
Working
Answer
There are (n choose r)(n choose (n-r)) = (n choose r)² selections with r adults, using (n choose (n-r)) = (n choose r). Adding over r gives ∑ᵣ₌₀ⁿ(n choose r)².
Conclude
Working
Answer
Both expressions count the same selections, so they are equal. blacksquare

Self-mark with the mark scheme

Tick each mark point that your answer includes.

Tick a point only if your written proof contains it. This self-check does not record a mark.

Mark points

1 mark: Counts the selections of n people from 2n directly as C(2n, n).
1 mark: Splits by the number r of adults and says the cases r = 0, …, n are disjoint and exhaustive.
1 mark: Counts each case as C(n, r) × C(n, n − r) and uses C(n, n − r) = C(n, r) to get C(n, r)².
1 mark: States that both sides count the same set, so they are equal.

Common mistake

Checking n = 6 (924 on both sides) supports the identity but proves nothing. Without saying that each selection has exactly one value of r, the sum could double-count or miss selections.

Common mistakes

Applying the pigeonhole principle without saying what the pigeons and the boxes are.
Choosing boxes that do not guarantee the property, such as boxes that two objects can share without the required relationship.
Using the strong form wrongly: with kn + 1 objects in n boxes, some box has at least k + 1.
In a double-counting proof, counting two different sets instead of the same set twice.
Checking an identity for small n and calling that a combinatorial proof.

The symmetry principle is taught in The symmetry principle.

Syllabus and review details

GCE A-Level H3 Mathematics 2027 · 2027

Last reviewed: 2026-11-06

Read offline with Premium

Guided steps

Reading settings

The pigeonhole principle

Five points in a square

Choose the boxes

Apply the principle

A coprime pair

Define the boxes

Show consecutive integers are coprime

Count the same set in two ways

A committee with a chair

The sum of squared binomial coefficients

Count directly

Count by the number of adults

Conclude

Common mistakes

Lesson done

The pigeonhole principle

Five points in a square

A coprime pair

Count the same set in two ways

A committee with a chair

The sum of squared binomial coefficients

Common mistakes

Questions