Lesson · Combinatorics and Counting · Corrections

The Generalised Pigeonhole Principle

With n objects in k boxes, some box holds at least ⌈n/k⌉. Sets, Relations, and Functions stated it; here it is applied to monotone subsequences and to the Ramsey number R(3,3) = 6.

Open the interactive lesson Practice

n objects, k boxes ⟹ some box has ≥ ⌈n/k⌉ Erdős–Szekeres: any sequence of n²+1 distinct reals has a monotone subsequence of length n+1 R(3,3) = 6: any 2-colouring of K₆ has a monochromatic triangle

One bound, two theorems

Core ideas

What this lesson establishes

The principle is elementary. The theorems it proves are not, and the gap between the two is the point of this lesson.

The bound rounds up

20 objects into 6 boxes guarantees a box with 4, not 3. Rounding down gives a claim that is true but weaker than what holds.

Choosing the boxes is the whole difficulty

In Erdős–Szekeres the boxes are pairs of subsequence lengths, which is not a classification anyone would guess.

It gives certainty, not likelihood

Six people always contain three mutual acquaintances or three mutual strangers. No probability is involved.

The material

The principle, applied

Statement, then two theorems whose proofs are pigeonhole with a clever classification.

Theorem · Generalised pigeonhole principle

If n objects are placed into k boxes, some box contains at least ⌈n/k⌉ objects.

If every box held at most ⌈n/k⌉ − 1, the total would be at most k(⌈n/k⌉ − 1) < k(n/k + 1 − 1) = n, using ⌈n/k⌉ < n/k + 1. That contradicts having placed all n.

□

Example · Basic applications

Among 100 people, at least ⌈100/12⌉ = 9 share a birth month. In any set of 10 integers, at least ⌈10/2⌉ = 5 share a parity. Each is one division.

Monotone subsequences

Theorem · Erdős-Szekeres

Every sequence of n² + 1 distinct real numbers contains a monotone subsequence of length n + 1 — increasing or decreasing.

For each position i, let aᵢ be the length of the longest increasing subsequence ending at i, and bᵢ the length of the longest decreasing one ending at i.

Suppose no monotone subsequence of length n+1 exists. Then every aᵢ and every bᵢ lies in {1, …, n}, so the pair (aᵢ, bᵢ) takes one of n² values. With n² + 1 positions, two positions i < j share a pair.

But that is impossible. If xᵢ < xⱼ then the increasing subsequence ending at i extends to j, so aⱼ > aᵢ. If xᵢ > xⱼ then bⱼ > bᵢ. Either way the pairs differ.

□

The boxes are the n² possible pairs (aᵢ, bᵢ), and inventing them is the entire proof. Once the classification is chosen, the pigeonhole principle does the rest in one line. This is the lesson's real content: the principle is trivial and the classification is not.

A Ramsey number

Theorem · R(3,3) = 6

Among any six people, three are mutual acquaintances or three are mutual strangers. Five people do not suffice.

Take a person P. Each of the other five is an acquaintance or a stranger, so by pigeonhole at least ⌈5/2⌉ = 3 fall in one class; say three acquaintances A, B, C.

If any two of A, B, C know each other, they and P are three mutual acquaintances. If no two of them do, A, B, C are three mutual strangers.

For five people it can fail: arrange them in a circle where each knows exactly the two neighbours. That has no triangle of either kind.

□

Both halves are needed. The construction on five people is what makes the theorem say R(3,3) = 6 rather than R(3,3) ≤ 6, and producing such constructions is generally much harder than the pigeonhole bound.

Ramsey numbers grow ferociously and are almost entirely unknown. R(4,4) = 18; R(5,5) is only known to lie between 43 and 46, despite decades of effort. Erdős's remark is the standard one: if aliens demanded R(5,5) we should marshal all our computers, and if they demanded R(6,6) we should attack them instead.

Interactive

The four counting rules

Enumerated while enumeration is possible

The triangles the theorem is about

At n = 6, r = 3 the list is the 20 triples among six people — the candidate triangles in the proof of R(3,3) = 6. Set r = 2 for the 15 pairs, each of which is coloured acquaintance or stranger; the theorem says that however the 15 are coloured, one of the 20 triples is a single colour. At n = 5 there are 10 triples and 10 pairs, and the five-cycle colours the pairs so that no triple is. A count is not the argument, but it is the object the argument ranges over.

n (things to choose from)5

r (things chosen)3

Highlight and enumerate

Method

Constructing a pigeonhole argument

Objects are usually given; boxes are invented.

Identify the objects

The people, the numbers, the positions in the sequence. Usually explicit in the problem.

Invent the classification

The hard step. Remainders, parities, degree counts, pairs of subsequence lengths — whatever gives fewer boxes than objects.

Compute ⌈n/k⌉

Round up. This is the guaranteed occupancy, and rounding down weakens the conclusion for no reason.

State what a full box gives you

Two objects in one box must yield the conclusion. If it does not, the classification was the wrong one.

Generalised pigeonhole

Score 0 / 0

Choose the answer you can justify.

A block summing to a multiple of n

Given any n integers, some consecutive block sums to a multiple of n.

Let a₁, …, aₙ be the integers and define the partial sums s₁ = a₁, s₂ = a₁+a₂, …, sₙ = a₁+…+aₙ Consider their remainders mod n. CASE 1 some sⱼ ≡ 0 (mod n). Then the block a₁ + … + aⱼ works. CASE 2 no sⱼ ≡ 0. Then the n remainders lie in {1, …, n−1}, which is n objects in n−1 boxes. So sᵢ ≡ sⱼ for some i < j, and sⱼ − sᵢ = a_{i+1} + … + aⱼ ≡ 0 (mod n). ∎

The classification is "remainder mod n", and case 1 is what reduces the box count from n to n − 1 — the same move as the acquaintance-count argument in Sets, Relations, and Functions. Creating a surplus by ruling out one box is the recurring trick.

Common mistakes

Rounding the bound downIt is ⌈n/k⌉. With 20 objects in 6 boxes the guarantee is 4, and claiming 3 throws away part of the theorem.

Choosing more boxes than objectsA finer classification proves less. The boxes must be fewer than the objects for anything to follow.

Proving only the upper bound of a Ramsey-type resultR(3,3) ≤ 6 is the pigeonhole half. Equality needs a construction on five people, and that half is usually the harder one.

Check your understanding

✓

Finish when you can invent a classification for a new problem.

Show that among any 5 points in a unit square, two are within √2 / 2 of each other — then improve the bound by choosing a finer partition and see what it costs you in the object count.

Note: Ramsey theory is the study of how much order is unavoidable in large structures. The pigeonhole principle is its simplest instance, and its characteristic feature is already visible here: the bounds are enormous and the exact values are almost always unknown.