When pigeons outnumber pigeonholes, some birds must double up. This obvious statement — and its inverse — have deep connections to many areas of math and computer science.
They say a bird in the hand is worth two in the bush, but for computer scientists, two birds in a hole are better still. That’s because those cohabiting birds are the protagonists of a deceptively simple mathematical theorem called the pigeonhole principle. It’s easy to sum up in one short sentence: If six pigeons nestle into five pigeonholes, at least two of them must share a hole. That’s it — that’s the whole thing.
“The pigeonhole principle is a theorem that elicits a smile,” said Christos Papadimitriou(opens a new tab), a theoretical computer scientist at Columbia University. “It’s a fantastic conversation piece.”