If more than n objects go into n boxes, some box gets at least two. More generally, more than kn objects in n boxes force some box to hold k + 1. It sounds obvious, but choosing the right boxes proves surprising guarantees.
The art is in the boxes: remainders on division, pairs that add to a target, colours, halves of a square, chains of numbers that divide each other.
When to try it
The question says ‘must there be’, ‘be certain’ or ‘guarantee’.
You are asked for the smallest number that forces something to happen.
There are more objects than obvious categories.
Watch out: To show a number is the smallest that works, also give an example with one fewer where it fails.
Two worked examples
Try each one first. The hints and the full solution are underneath.
Problem J82
Junior · CombinatoricsMultiple choiceSolved
A jar holds lots of red, green, blue and yellow sweets. Without looking, Tom takes sweets one at a time. What is the smallest number he must take to be certain of having three sweets of the same colour?
Hint
What is the worst that could happen?
Second hint
He could take two of every colour without having three of any.
Full worked solution
Answer: C, 9
Worst case: Tom takes 2 red, 2 green, 2 blue and 2 yellow: 8 sweets and still no three the same.
So 8 is not enough.
With 9 sweets in 4 colours, if every colour had at most 2 there would be at most 8 sweets. So some colour has at least 3.
The answer is 9 (C).
Why this works: To be certain, imagine the worst case. The pigeonhole principle then guarantees the result one step later.
Where it leads: In general, to be sure of k of one colour with c colours you need c(k − 1) + 1 items. The same principle proves that two Londoners have exactly the same number of hairs.
What is the smallest number of different whole numbers you must choose from 1 to 30 to be certain that two of the chosen numbers have a sum divisible by 7?
Hint
Group the numbers by their remainder on division by 7. Which remainders add up to a multiple of 7?
Second hint
Remainders 1 and 6, 2 and 5, 3 and 4 pair up; two numbers with remainder 0 also work.
Full worked solution
Answer: 16
Two numbers have a sum divisible by 7 when their remainders are (0, 0), (1, 6), (2, 5) or (3, 4).
From 1 to 30: remainder 0: 4 numbers; 1: 5; 2: 5; 3: 4; 4: 4; 5: 4; 6: 4.
Largest set with no such pair: all of remainder 1 (5), all of remainder 2 (5), all of remainder 3 or 4 (4), and at most one multiple of 7 (1): 15 numbers.
So 15 is not enough, but any 16 numbers must contain a good pair: the answer is 16.
Why this works: The pigeonhole principle with carefully chosen ‘holes’ (pairs of remainders) gives the guarantee; an explicit 15-number set shows nothing smaller works.
Where it leads: Erdős–Ginzburg–Ziv: among any 2n − 1 whole numbers, some n of them have a sum divisible by n.
CBSE Math Revision