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. But the pigeonhole principle isn't just for the birds. Even though it sounds painfully straightforward, it's become a powerful tool for researchers engaged in the central project of theoretical computer science: mapping the hidden connections between different problems. The pigeonhole principle applies to any situation where items are assigned to categories, and the items outnumber the categories. For example, it implies that in a packed football stadium with 30,000 seats, some attendees must have the same four-digit password, or PIN, for their bank cards. Here the...
learn more
