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.
LEARN MORE

Difference between revisions of "Pigeonhole Principle"

m (YELP, examples speak better than lectures, do any of you know quality pigeonhole problems?)
(Examples)
Line 6: Line 6:
  
 
Can users find some?
 
Can users find some?
 +
 +
You could paste in [http://www.upal.ca/adeel/problems/2006/4/9.pdf these]... (maybe, just a suggestion)

Revision as of 20:29, 17 June 2006

Pigeonhole Principle

The basic pigeonhole principle says that if there are $n$ holes, and $n+k$ piegons (k>1), then one hole MUST contain two or more pigeons. The extended version of the pigeonhole principle states that for n holes, and $nk+j$ 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)