Posts Tagged ‘pegionhole principle’

Pigeonhole Principle

Posted by guptaradhesh on November 25, 2010

I wondered why I didn’t study this in my academics. Although it seems I have found this mentioned somwhere in the discussions. I liked the description given on wiki and some other urls.

I am imitating some part text for the places which I believe should be useful for a ‘peek look and move ahead’ crawler.


The pigeonhole principle states that if n items are put into m pegeonholes with n > m, then at least one pigeonhole must contain more than one item.

That is, if there is a mapping between two finite sets of unequal size, then at least one element in the smaller set must be paired with more than one element in the larger set.

The extended pigeonhole principle says that if p > nh for some integer n, then at least one hole will contain n + 1 pigeons.

(despite seeming intuitive it can be used to demonstrate possibly unexpected results)

Some common fun applications of Pegionhole Principle are as:

– At any given time in NY there lives at least two people with the same numbe of hairs

– Some prople reading this blog will have the same birthday (birthday paradox)

– If you pick five cards from a standard deck of 52 cards, then atleast two will be of the same suit

. . . . .


Posted in puzzles/ algorithms | Tagged: , , | 2 Comments »