The Pigeonhole Principle, With Olympiad Problems

The pigeonhole principle sounds almost too obvious to be useful: if you put more pigeons than holes into a set of pigeonholes, some hole gets at least two pigeons. Yet it is one of the most powerful ideas in competition maths, and it turns up in olympiads at every level, from school contests to the International Mathematical Olympiad. The trick is never the principle itself. It is spotting what the pigeons and the holes should be.

This guide explains the principle, its general form, and works through four classic competition-style problems. Because some of these results are genuinely surprising, we checked them in Python, including one claim verified against every one of 59,049 possible cases, and ran simulations to show the difference between what is likely and what is guaranteed.

The principle

If n + 1 or more objects are placed into n boxes, at least one box contains at least two objects. That is all. You do not know which box, and you do not know which two objects. You only know it must happen. That kind of existence argument, proving something is there without finding it, is exactly what makes the principle so useful in proofs.

• In any group of 13 people, at least two were born in the same month. (13 people, 12 months.)
• Pull 3 socks from a drawer of black and white socks, and you are guaranteed a matching pair. (3 socks, 2 colours.)
• In a city of a million people, at least two have exactly the same number of hairs on their head, because nobody has anywhere near a million hairs.

The general version

A stronger form tells you how full the fullest box must be: if n objects go into k boxes, at least one box contains at least n ÷ k objects, rounded up. With 50 socks in 3 colours, some colour appears at least 17 times, because 50 ÷ 3 is 16.67, which rounds up to 17.

Problem 1: remainders

Problem. Show that among any 8 whole numbers, two of them differ by a multiple of 7.

Solution. Every whole number leaves one of 7 remainders when divided by 7: 0, 1, 2, 3, 4, 5 or 6. Those are the boxes. With 8 numbers and 7 boxes, two numbers share a remainder. Two numbers with the same remainder differ by a multiple of 7. Done.

Here it is with 8 random three-digit numbers, grouped by remainder:

import random

# any 8 whole numbers: at least two leave the same remainder when divided by 7,
# so their difference is a multiple of 7
random.seed(11)
numbers = random.sample(range(100, 1000), 8)
by_remainder = {}
for n in numbers:
    by_remainder.setdefault(n % 7, []).append(n)

print("numbers:", numbers)
for r, group in sorted(by_remainder.items()):
    if len(group) > 1:
        a, b = group[:2]
        print(f"remainder {r}: {a} and {b}, difference {abs(a - b)} = 7 x {abs(a - b) // 7}")

numbers: [563, 986, 673, 977, 899, 576, 562, 620]
remainder 2: 576 and 562, difference 14 = 7 x 2
remainder 3: 563 and 899, difference 336 = 7 x 48
remainder 4: 977 and 620, difference 357 = 7 x 51

Whatever 8 numbers you choose, at least one remainder box will contain two of them. This remainder trick is behind a large share of olympiad number theory problems.

Problem 2: a block that sums to a multiple of n

Problem. Show that any list of n whole numbers contains a block of consecutive numbers whose sum is a multiple of n.

Solution. Write down the running totals: the first number, the first two added, the first three, and so on, n totals in all, plus a starting total of 0, making n + 1 totals. Divide each by n. There are only n possible remainders, so two totals share a remainder. Their difference, which is exactly the sum of the numbers between them, is a multiple of n.

This one is surprising enough to be worth checking completely. The program below tries every possible list of 5 numbers from 1 to 9, all 59,049 of them:

from itertools import product

def has_block_divisible(nums):
    # prefix sums: if two share a remainder mod n, the numbers between them sum to a multiple of n
    n, total, seen = len(nums), 0, {0: -1}
    for i, x in enumerate(nums):
        total += x
        if total % n in seen:
            return nums[seen[total % n] + 1: i + 1]
        seen[total % n] = i
    return None

# check EVERY list of 5 numbers taken from 1..9: 9^5 = 59,049 lists
failures = [nums for nums in product(range(1, 10), repeat=5) if has_block_divisible(list(nums)) is None]
print("lists checked:", 9 ** 5, "  lists with no block summing to a multiple of 5:", len(failures))
print("example: [3, 9, 1, 8, 6] ->", has_block_divisible([3, 9, 1, 8, 6]))

lists checked: 59049   lists with no block summing to a multiple of 5: 0
example: [3, 9, 1, 8, 6] -> [9, 1]

Not a single failure, exactly as the proof guarantees. Notice that checking cases is not a proof in general, because there are infinitely many possible lists. The pigeonhole argument covers all of them at once. The computer check is what mathematicians call evidence, and the argument is what makes it certain.

Problem 3: five points in a square

Problem. Five points are placed anywhere inside a square with side 1. Show that two of them are at most √2 ÷ 2, about 0.707, apart.

Solution. Divide the square into four smaller squares with side 1/2. Five points, four small squares: two points lie in the same small square. The farthest apart two points in a square of side 1/2 can be is its diagonal, which is √2 ÷ 2. So those two points are at most that far apart.

A simulation agrees. Placing five random points twenty thousand times, the closest pair was never further apart than the guarantee:

import random, math
from itertools import combinations

random.seed(2)
worst = 0
for trial in range(20_000):
    points = [(random.random(), random.random()) for _ in range(5)]
    closest = min(math.dist(p, q) for p, q in combinations(points, 2))
    worst = max(worst, closest)
print(f"largest 'closest pair' distance seen in 20,000 random tries: {worst:.3f}")
print(f"the guarantee from the pigeonhole principle:                 {math.sqrt(2) / 2:.3f}")

largest 'closest pair' distance seen in 20,000 random tries: 0.541
the guarantee from the pigeonhole principle:                 0.707

Likely versus guaranteed: the birthday puzzle

It is worth being clear about what the principle does not do. It gives certainty, not likelihood. The famous birthday problem shows the difference: in a group of just 23 people, there is roughly a 50% chance that two share a birthday. That is probability. For a guarantee, you need one more person than there are possible birthdays, 367 including 29 February.

import random

def shared_birthday(people):
    days = [random.randrange(366) for _ in range(people)]   # include 29 February
    return len(set(days)) < people

random.seed(5)
for people in (10, 23, 50, 367):
    trials = 20_000
    share = sum(shared_birthday(people) for _ in range(trials)) / trials
    print(f"{people:>3} people: two share a birthday in {share:.1%} of {trials:,} simulated groups")

 10 people: two share a birthday in 11.5% of 20,000 simulated groups
 23 people: two share a birthday in 50.4% of 20,000 simulated groups
 50 people: two share a birthday in 96.9% of 20,000 simulated groups
367 people: two share a birthday in 100.0% of 20,000 simulated groups

Olympiad problems ask for certainty, which is why they are about pigeonholes rather than probability. If you enjoy the probability side too, it is a whole topic of its own.

How to get better at pigeonhole problems

1. Look for the words "must", "at least" and "always". They usually mean an existence proof, and pigeonhole is the first tool to try.
2. Count first. How many objects are there, and how many boxes would make the argument work? Often the numbers in the question tell you: 8 numbers and 7 remainders is not a coincidence.
3. Try common boxes: remainders, parity (odd or even), colours, regions of a shape, ranges of values.
4. Write the argument in three sentences: what the boxes are, why there are more objects than boxes, and what sharing a box gives you.
5. Check small cases with code when a claim surprises you, as we did above. It builds confidence and sometimes reveals a pattern for the proof.

For how pigeonhole fits into olympiad preparation more broadly, see our guides to IOQM, RMO and INMO preparation and maths olympiad training. For the computer science side, number theory like this appears in contests such as USACO.

The principle takes a sentence to state. The skill is seeing which boxes the problem is quietly offering you.

How we teach it

In our olympiad preparation, students attempt a problem before seeing any method, in line with the approach on our how we teach page of deriving a rule before it is written down, and they write every proof in their own words. See IOQM, RMO and INMO preparation and maths olympiad and AMC tutoring, taught live, one to one or in small groups of 5 to 10.

Frequently asked questions