Pigeonhole principle

Fitting ten pigeons in nine holes -one hole will contain more than one pigeon

The pigeonhole principle explains that when there are (n) pigeon-sized holes in a pigeon container, then it's impossible to fit more than (n) pigeons in that container, without having at least one hole containing more than one. The pigeons are used here as an example for anything that can be put into containers or subdivisions.

This theorem is important in computer science and mathematics, especially in graph theory.

Example

In one suitcase there are 12 blue socks and 18 black socks. If we close our eyes, how many socks must we pull out to be sure we have a pair of the same color?

If we think of the colors as holes or categories, we have 2 holes, so (n) = 2. If we pull three socks from the suitcase, at least two of them must be the same color, because 3 is a number greater than 2. So the correct answer here is three.