---
title: "The Pigeonhole Principle: 4 Olympiad Problems Solved"
description: "The pigeonhole principle explained with four olympiad-style problems, the general version, and results checked in Python across 59,049 cases."
slug: pigeonhole-principle-explained
canonical: https://learn.modernagecoders.com/blog/pigeonhole-principle-explained/
date: 2026-09-28
dateModified: 2026-09-28
category: "Mathematics"
tags: ["Mathematics", "Olympiad", "Problem Solving", "Proof"]
keywords: ["pigeonhole principle", "pigeonhole principle explained", "pigeonhole principle problems", "generalized pigeonhole principle", "pigeonhole principle olympiad", "pigeonhole principle examples", "birthday problem vs pigeonhole"]
readTime: "8 min read"
author: "Modern Age Coders Team"
---
# The Pigeonhole Principle, With Olympiad Problems

> A one-sentence idea that solves surprisingly hard problems: the principle, its general form, four classic problems with full solutions, and the results checked in code.

![The pigeonhole principle: five objects placed into four boxes, so one box holds two](/images/blog/pigeonhole-principle-explained/00-hero.png)

*By Modern Age Coders Team · 2026-09-28 · 8 min read*

**Quick answer:** The pigeonhole principle says that if more objects than boxes are placed into boxes, some box holds at least two, and more generally n objects in k boxes means some box has at least n divided by k, rounded up. It proves that something must exist without finding it, which makes it a core olympiad technique. The skill is choosing the boxes: remainders, colours, regions of a shape or ranges of values. It gives certainty, unlike probability arguments such as the birthday problem.

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.

![The general pigeonhole principle: n items into k boxes means some box has at least n divided by k rounded up, with three examples](/images/blog/pigeonhole-principle-explained/01-general.png)

*The formula is easy. Choosing the boxes is the real skill.*

> **The question to ask every time**

> When a problem says "prove that there must be..." or "show that at least two...", ask: what could the boxes be? Remainders, colours, regions of a shape, ranges of numbers and days of the week are the most common answers.

## 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:

**remainders.py**

```python
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}")
```

**Output**

```text
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:

**consecutive_block.py**

```python
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]))
```

**Output**

```text
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.

![Five points in a unit square divided into four smaller squares, with two points forced into the same small square](/images/blog/pigeonhole-principle-explained/02-square.png)

*Four regions, five points: two must share a region.*

**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:

**five_points.py**

```python
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}")
```

**Output**

```text
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.

**birthdays.py**

```python
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")
```

**Output**

```text
 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
```

![Simulated chance of a shared birthday for groups of 10, 23, 50 and 367 people](/images/blog/pigeonhole-principle-explained/03-birthdays.png)

*Probability rises quickly. Certainty needs the pigeonhole principle.*

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](/ioqm-rmo-inmo-preparation) and [maths olympiad training](/maths-olympiad-training-uk). For the computer science side, number theory like this appears in contests such as [USACO](/blog/usaco-bronze-to-silver-what-blocks-most-students).

> 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](/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](/ioqm-rmo-inmo-preparation) and [maths olympiad and AMC tutoring](/math-olympiad-amc-tutoring), taught live, one to one or in small groups of 5 to 10.

[Book a free class](/book-demo) [Book a priority demo](/book-demo)

## Frequently asked questions

**What is the pigeonhole principle?**

If you put more objects into boxes than there are boxes, at least one box must contain more than one object. For example, among 13 people at least two share a birth month, because there are only 12 months.

**What is the generalised pigeonhole principle?**

If n objects are placed into k boxes, at least one box contains at least n divided by k objects, rounded up. With 50 socks in 3 colours, some colour appears at least 17 times.

**Why is the pigeonhole principle useful in olympiads?**

It proves that something must exist without finding it. Many olympiad problems ask you to show that two numbers, points or people must share a property, and choosing the right boxes turns a hard-looking problem into a short proof.

**How do you choose the pigeonholes?**

Look at what the problem wants two objects to share. Common choices are remainders when dividing by a number, odd or even, colours, regions of a shape, and ranges of values. The numbers in the problem often hint at how many boxes you need.

**Is the pigeonhole principle the same as the birthday problem?**

No. The birthday problem is about probability: 23 people share a birthday about half the time. The pigeonhole principle gives certainty: 367 people guarantee a shared birthday, counting 29 February.

**At what level does the pigeonhole principle appear?**

It appears in junior olympiads and school challenges as simple puzzles, in national olympiads such as RMO and BMO as a key proof technique, and at the International Mathematical Olympiad in more subtle forms.

**Can a computer prove the pigeonhole principle?**

A computer can check many cases, like the 59,049 lists in this post, which is useful evidence. But a proof covers every possible case at once, including infinitely many, which is why the pigeonhole argument itself is needed.

---

*Source: https://learn.modernagecoders.com/blog/pigeonhole-principle-explained/*