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.
Difference between revisions of "Pigeonhole Principle"
IntrepidMath (talk | contribs) |
IntrepidMath (talk | contribs) m (YELP, examples speak better than lectures, do any of you know quality pigeonhole problems?) |
||
| Line 2: | Line 2: | ||
The basic pigeonhole principle says that if there are <math>n</math> holes, and <math>n+k</math> 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. | The basic pigeonhole principle says that if there are <math>n</math> holes, and <math>n+k</math> 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? | ||
Revision as of 21:28, 17 June 2006
Pigeonhole Principle
The basic pigeonhole principle says that if there are 
holes, and 
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?
