The Pigeonhole Principle

Back to Math-CS

If you put more than n pigeons into n pigeonholes, then at least one pigeonhole will have more than one pigeon.

Given two sets A and B, with |A| = m > n = |B|, for any function ƒ: A->B, there exists b in B s.t. | {x in A: ƒ(x)=b} | > 1. In general form, | {x in A: ƒ(x)=b} | ≥ ceil(m/n). Dijkstra's form says for a nonempty finite collection of integers, the max value is at least the average value.


People have on average 100,000 hairs and at most 700,000 hairs. If there are 760,000 people, the pigeonhole principle says that at least two people have the same number of hairs.