insideout Get Pro

03 · The pigeonhole principle

Free

Puzzles and Brainteasers, lesson 3

The pigeonhole principle

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.

Part 1. More items than boxes

Find how many items guarantee a match by building the worst case.

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?

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

Find the fewest socks that guarantee a pair, with 4 colours.

  1. Name the boxes4 colours = 4 boxes

    Each sock you draw drops into the box for its colour.

  2. Build the worst case1 + 1 + 1 + 1 = 4 socks, no pair

    The unluckiest draw puts one sock in each box. So 4 socks guarantee nothing.

  3. Add one more5 socks, 4 boxes

    Every box already holds a sock, so the fifth lands on top of one. That's a pair.

Answer5 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.

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?

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

Choose boxes, such as remainders, so that any two items in one box give what you want.

Guess first

Pick any 6 whole numbers. Must two of them differ by a multiple of 5?

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

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 boxesremainders 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 in17 → 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 pair42 − 17 = 25 = 5 × 5

    Two numbers with the same remainder differ by whole fives, since the remainders cancel when you subtract.

AnswerAlways: two share a remainder, and they differ by a multiple of 5.

60remainder 031remainder 11742remainder 28remainder 399remainder 4divide by 5, keep the remainder42 − 17 = 25 = 5 × 5
0123460311742899remainder after dividing by 542 − 17 = 25 = 5 × 5same box, so they differ by fives
Figure 1Six 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?

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

Find the fullest box you can promise when many items share a few boxes.

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?

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

Show that some two of any 5 points in the square are no more than 0.71 metres apart.

  1. Make 4 boxes4 squares, ½ metre on a side

    Cut the square in half both ways. A point on a cut line can go in either box.

  2. Count5 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 tightcorners + 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.

AnswerYes: some two are at most √2 / 2 ≈ 0.707 metres apart.

½ m½ m½ mdiagonal of a small square: √2 / 2 ≈ 0.71 m
Figure 2Four 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.

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?

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.

Check the boxes by brute force
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

Four questions from across the lesson. Try each one before you look back.

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?

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.

2

Pick any 3 whole numbers. Must two of them have an even sum?

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.

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?

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.

4

At a meeting of 50 people, some pairs shake hands. Must two people have shaken the same number of hands?

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. 1More items than boxes

    Guaranteed means the worst case: with 4 sock colours the worst draw holds one of each, so 5 socks make a sure pair.

  2. 1More items than boxes

    Show both halves: a worst case with one item fewer and no match, and the count that forces one.

  3. 2Choose the boxes

    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. 3The general form

    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.

Puzzles and Brainteasers overviewSpotted a mistake? Tell us.