The Pigeonhole Principle

4 10 2006

It’s an almost obvious statement which says:

“If there are N pigeonholes and N+1 or more pigeons, then at least one pigeonhole is occupied by more than one pigeon”

Easy, right? OK, now excercise: What is the minimum number of socks that should be taken from a shelve containing red, blue, and white socks, to ensure that you get a pair of socks with the same color?

The answer is four. In this case, there are 3 pigeonholes (one for each color), and to be sure of getting two socks (pigeons) with the same color (in the same pigeonhole), all we have to do is to grab 4 (= 3 + 1) socks from the shelve.

OK, bonus problem: Find the minimum number of elements that one needs to take from the set S = {1,2,3,…9} to be sure that two of the numbers add up to 10.

Source: Schaum’s Outline of Theory and Problems of Discrete Mathematics, 2nd edition.

–edit: it is also known as Dirichlet’s box principle–




Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: