Mathematics

Pigeonhole Principle

If more items are placed into fewer containers, at least one container holds more than one item.

Trivially obvious and surprisingly powerful, because it produces existence proofs without construction.

Generalised form: n items in k boxes force some box to hold at least ceiling(n/k).

Interview uses. Any two of thirteen people share a birth month. In any group of six, three are mutual acquaintances or three are mutual strangers. Among any n+1 integers from 1 to 2n, two are coprime and one divides another.

The skill being tested is choosing what plays the role of pigeons and what plays the role of holes - which is rarely obvious and is the whole problem.

Related terms

Practise this

Put it into practice

Knowing the definition is not the same as spotting where it applies under time pressure. Work the question bank free.

Start practising free

Browse the full quant interview glossary