# The pigeonhole principle

Puzzles and Brainteasers, lesson 3. Free.

URL: https://insideout.sh/courses/puzzles/03
Updated: 2026-11-12T09:52:14Z
More items than boxes means some box holds two.

Some puzzles ask you to prove that something must happen, however things fall. One idea settles many of them: put more items into boxes than there are boxes, and some box gets two. The skill is choosing the boxes. You need division with remainders and nothing else.

By the end, you can:
1. Find how many items guarantee a match by building the worst case.
2. Choose boxes, such as remainders, so that any two items in one box give what you want.
3. Find the fullest box you can promise when many items share a few boxes.

## Part 1. More items than boxes

**Guess first:** A drawer holds loose socks in 4 colours, plenty of each. In the dark, how many must you take out to be sure of two of the same colour?
A. 8
B. 5
C. 4
D. 2
Answer: B. 5. With 4 you could be unlucky and hold one of each colour. The fifth has to match one of them.

"Be sure" means the answer has to work on your unluckiest day. So don't ask what usually happens. Build the worst draw you can, and see where it breaks.

**Example 1.1: Socks in the dark**
Problem: Find the fewest socks that guarantee a pair, with 4 colours.
1. Name the boxes: 4 colours = 4 boxes (Each sock you draw drops into the box for its colour.)
2. Build the worst case: 1 + 1 + 1 + 1 = 4 socks, no pair (The unluckiest draw puts one sock in each box. So 4 socks guarantee nothing.)
3. Add one more: 5 socks, 4 boxes (Every box already holds a sock, so the fifth lands on top of one. That's a pair.)
Answer: 5 socks.

Both halves matter. The worst case shows 4 isn't enough, and the count shows 5 always is. Together they make 5 the exact answer.

**The pigeonhole principle**: If more items than boxes go into the boxes, some box holds at least two. It promises a crowded box, but not which one.
Rule: k + 1 items in k boxes → some box holds 2

Guaranteed means the worst case, not the likely one. Two socks match a quarter of the time when the colours are equally common, which says nothing about being sure. Change the goal, and the worst case changes with it.

**Your turn:** Now the drawer holds exactly 10 black and 10 white socks. In the dark, how many must you take to be sure of two black socks?
A. 3
B. 4
C. 11
D. 12
Answer: D. The worst case takes all 10 white socks first, then 2 black: 12. Three socks guarantee a pair of some colour, not a black pair. The answer 11 forgets that you need two black ones.

## Part 2. Choose the boxes

**Guess first:** Pick any 6 whole numbers. Must two of them differ by a multiple of 5?
A. Only if some are bigger than 5
B. Yes, always
C. Usually, but not always
D. Only if two are close together
Answer: B. Yes, always. Divide each by 5: there are only 5 possible remainders and 6 numbers, so two share a remainder, and their difference is a multiple of 5.

Here the items are given, but nothing says what the boxes are. You choose them, and the right boxes make "two in one box" mean exactly what the puzzle asks for.

**Example 2.1: Six numbers, five remainders**
Problem: Show that among any 6 whole numbers, two differ by a multiple of 5. Try it on 17, 42, 8, 99, 31 and 60.
1. Choose the boxes: remainders 0, 1, 2, 3, 4 (Divide by 5 and keep the remainder. Every whole number lands in one of these 5 boxes.)
2. Drop the numbers in: 17 → 2, 42 → 2, 8 → 3, 99 → 4, 31 → 1, 60 → 0 (Six numbers, five boxes, so some box gets two. Here it's box 2.)
3. Read the pair: 42 − 17 = 25 = 5 × 5 (Two numbers with the same remainder differ by whole fives, since the remainders cancel when you subtract.)
Answer: Always: two share a remainder, and they differ by a multiple of 5.

Figure 1: Six numbers in five remainder boxes. Two must share a box, and any two in one box differ by a multiple of 5.

**Modulo**: **a mod n**, read "a modulo n", is the remainder when you divide a by n: 42 mod 5 = 2. Two numbers with the same remainder mod n differ by a multiple of n.

Boxes chosen badly prove nothing. Sort the six numbers by size instead, 1 to 20, 21 to 40 and so on, and two may share a box, but their difference can be anything. Before you count, ask what two items in one box would give you.

**Your turn:** Pick any 6 different numbers from 1 to 10. Must two of them add up to 11?
A. Yes, always
B. Only if you pick 7 or more
C. No: 1, 2, 3, 4, 5 and 6 avoid it
D. Only if you pick both 5 and 6
Answer: A. Make the boxes the pairs that add to 11: 1 and 10, 2 and 9, 3 and 8, 4 and 7, 5 and 6. Five boxes, six numbers, so some box gets both its numbers. In 1, 2, 3, 4, 5 and 6, the 5 and 6 add to 11.

## Part 3. The general form

**Guess first:** Drop 5 points anywhere in a square 1 metre on each side, edges included. Must some two of them be no more than 0.71 metres apart?
A. Only if the points fall at random
B. No: they can all be 1 metre apart
C. Yes, always
D. No: put four in the corners and one in the middle
Answer: C. Yes. Cut the square into four smaller squares: two points share one, and two points in a small square are at most 0.71 metres apart. Four corners and the middle are the closest call, every pair at least 0.707 metres apart, still inside the limit.

There are no boxes in sight here, so make some. Cut the square into pieces small enough that any two points in one piece are close.

**Example 3.1: Five points, four small squares**
Problem: Show that some two of any 5 points in the square are no more than 0.71 metres apart.
1. Make 4 boxes: 4 squares, ½ metre on a side (Cut the square in half both ways. A point on a cut line can go in either box.)
2. Count: 5 points, 4 boxes (Some small square holds at least two of the points.)
3. Measure the box: √(½² + ½²) = √2 / 2 ≈ 0.707 m (The farthest apart two points in a small square can be is corner to corner. √2 / 2 is read "the square root of 2, over 2".)
4. Check it's tight: corners + centre: all ≥ 0.707 m (Four corners and the middle keep every pair at least 0.707 metres apart, so no smaller distance can be promised.)
Answer: Yes: some two are at most √2 / 2 ≈ 0.707 metres apart.

Figure 2: Four small squares, five points. Two must share a square, and two points in a small square are never farther apart than its diagonal, about 0.71 metres.

Put in more items and the promise grows. 50 people and 12 birth months guarantee a month shared by at least 5 people, because 12 months of 4 people hold only 48.

**The general pigeonhole principle**: If n items go into k boxes, some box holds at least n / k items, rounded up. ⌈x⌉, read "the ceiling of x", is x rounded up to a whole number: ⌈50 / 12⌉ = 5.
Rule: fullest box ≥ ⌈n / k⌉

The promise is about the fullest box only: some month could still have nobody. And round up, never down. 50 / 12 is about 4.2, and 4 people per month leaves 2 over.

**Your turn:** Drop 9 points in the same 1 metre square, cut into the same four small squares. At least how many points must one small square hold?
A. 3
B. 4
C. 1
D. 2
Answer: A. 9 points in 4 boxes: 9 / 4 = 2.25, rounded up is 3. Four squares of 2 hold only 8, so the ninth makes a 3. The answer 2 rounds down: it's true, but it isn't the most you can promise.

## Where you'll meet it

> **In interviews**: Pigeonhole questions tend to announce themselves with "must", "guarantee" and "at least". The interviewer wants the worst case and a reason. Say the boxes out loud before you count, then show the worst case with one item fewer, so your number is exact.

> **On the job**: No lossless compressor can shrink every file. There are 256 files of exactly 8 bits, but only 255 bit strings shorter than that, counting the empty one. If every 8-bit file got a shorter code, two would share one and couldn't both be restored. The same count says a hash with fewer values than inputs must have collisions.

```python
from itertools import combinations, product

# Socks in 4 colours: 4 socks can all differ, 5 never can
print(any(len(set(s)) == 4 for s in product(range(4), repeat=4)))  # True
print(all(len(set(s)) < 5 for s in product(range(4), repeat=5)))   # True

# 6 numbers: every way to fill the remainders 0 to 4 repeats one
print(all(len(set(r)) < 6 for r in product(range(5), repeat=6)))   # True

# 6 picks from 1 to 10 always hold a pair adding to 11
print(all(any(a + b == 11 for a, b in combinations(s, 2))
          for s in combinations(range(1, 11), 6)))                  # True

# Files of 8 bits against every shorter bit string
print(2 ** 8, sum(2 ** k for k in range(8)))                        # 256 255
```

Brute force can check a promise only when the cases can be listed, as remainders and picks can. For points in a square there are endless cases, and the boxes are the proof.

## Check yourself

**Question 1.** A bag holds counters in 3 colours, plenty of each. How many must you draw, without looking, to be sure of 3 of the same colour?
A. 9
B. 6
C. 4
D. 7
Answer: D. The worst case draws 2 of each colour, 6 counters with no three alike. The seventh makes a three. In the general form, 7 counters in 3 boxes give ⌈7 / 3⌉ = 3. The answer 6 is the worst case itself, one short.

**Question 2.** Pick any 3 whole numbers. Must two of them have an even sum?
A. Only usually
B. Only if one of them is even
C. No: try 1, 2 and 3
D. Yes, always
Answer: D. Use odd and even as the boxes: 3 numbers, 2 boxes, so two share a parity. Two odds or two evens add to an even number. In 1, 2 and 3, the 1 and the 3 add to 4.

**Question 3.** Counting 29 February, a birthday can fall on 366 days. How many people must be in a room to be sure two share a birthday?
A. 366
B. 183
C. 367
D. 23
Answer: C. Sure means the worst case: 366 people could all have different birthdays, so you need 367. With 23 people a shared birthday is only more likely than not, a chance and not a promise.

**Question 4.** At a meeting of 50 people, some pairs shake hands. Must two people have shaken the same number of hands?
A. Only if the number of handshakes is even
B. No: the counts 0 to 49 give 50 different boxes
C. Only if everyone shakes at least one hand
D. Yes, always
Answer: D. The counts run from 0 to 49, which looks like 50 boxes for 50 people. But 0 and 49 can't both happen: someone who shook every hand rules out someone who shook none. So at most 49 boxes are in use, and two people share one.

## What to remember

1. Guaranteed means the worst case: with 4 sock colours the worst draw holds one of each, so 5 socks make a sure pair.
2. Show both halves: a worst case with one item fewer and no match, and the count that forces one.
3. Choose boxes so that two in one box answer the puzzle: with remainders mod 5 as boxes, any 6 whole numbers hold two that differ by a multiple of 5.
4. n items in k boxes put at least ⌈n / k⌉ in some box, and 5 points in four small squares put two within √2 / 2 ≈ 0.71 metres.

Next: Next, finding one odd coin with a balance, by counting what each weighing can tell apart.
