Pigeonhole principle
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.
Worked example
A drawer holds 10 red, 10 blue and 10 black socks. In the dark, how many socks must you take to be sure of a matching pair?
Show the solution
- The colours are the holes: there are 3.
- With 3 socks you could have one of each colour, so 3 is not enough.
- With 4 socks in 3 colours, two must share a colour.
Answer: 4
Practise: 16 problems that use pigeonhole principle
Other strategies
Organised cases · Count the opposite · Working backwards · Invariants · Extremal principle · Parity and remainders · Symmetry · Spot the pattern and generalise · Proof techniques