CBSE Math Revision Start revising
Problem-solving strategy

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

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
  1. The colours are the holes: there are 3.
  2. With 3 socks you could have one of each colour, so 3 is not enough.
  3. 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

All strategy guides · Extension & competition maths