Pigeonhole principle
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.
Pigeonhole Principle Media
Pigeon-hole messageboxes at Stanford University
The pigeonhole principle gives an upper bound of 2n in the no-three-in-line problem for the number of points that can be placed on an n × n lattice without any three being colinear – in this case, 16 pawns on a regular chessboard
