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–

### Like this:

Like Loading...

*Related*

## Leave a Reply