The original version of this story appeared in Quanta Magazine.
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, a theoretical computer scientist at Columbia University. “It’s a fantastic conversation piece.”
But the pigeonhole principle