Pigeonhole principle

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[change | edit source]

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 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.