Learn more about the Pigeonhole Principle and other powerful techniques for combinatorics problems
in our Intermediate Counting
& Probability textbook by USA Math Olympiad winner (and MIT PhD) David Patrick.
Pigeonhole Principle
Revision as of 21:30, 17 June 2006 by Pianoforte (talk | contribs)
Pigeonhole Principle
The basic pigeonhole principle says that if there are 
holes, and 
pigons (k>1), then one hole MUST contain two or more pigeons. The extended version of the pigeonhole principle states that for n holes, and 
pigeons, j>1, some hole must contain k+1 pigeons. If you see a problem with the numbers n, and nk+1, think about pigeonhole.
Examples
Can users find some?
You could paste in these... (maybe, just a suggestion)
