What is Pigeonhole principle?
[[Image:TooManyPigeons.jpg|thumb|right|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.''' [[Category:Computer science]] [[Category:Mathematics]]