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?
"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.
- Name the boxes4 colours = 4 boxes
Each sock you draw drops into the box for its colour.
- 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.
- 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?
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?
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.
- 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.
- 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.
- 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.
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?
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?
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.
- 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.
- Count5 points, 4 boxes
Some small square holds at least two of the points.
- 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".
- 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.
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?
Where you'll meet it
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.
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.
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 255Brute 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?
2
Pick any 3 whole numbers. Must two of them have an even sum?
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?
4
At a meeting of 50 people, some pairs shake hands. Must two people have shaken the same number of hands?
What to remember
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.
1More items than boxes
Show both halves: a worst case with one item fewer and no match, and the count that forces one.
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.
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.