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"
m (proofreading) |
|||
| Line 14: | Line 14: | ||
| − | *Prove that having 100 whole numbers one can choose 15 of them so that the difference of any two is divisible by 7. (Manhattan Mathematical Olympiad 2005) | + | *Prove that having 100 whole numbers, one can choose 15 of them so that the difference of any two is divisible by 7. (Manhattan Mathematical Olympiad 2005) |
| Line 22: | Line 22: | ||
*Prove that among any ten points located on a circle with diameter 5, there exist at least two at a distance less than 2 from each other.(Japan 1997) | *Prove that among any ten points located on a circle with diameter 5, there exist at least two at a distance less than 2 from each other.(Japan 1997) | ||
| − | *Show that for any <math>{x\in\mathbb R}</math> and positive integer <math>{n}</math>, there exists a rational number <math>{\frac pq}</math> with <math>1\le q\le n</math> such that <math>\left|x-\frac pq\right|<\frac 1{nq}</math> (the classical Rational Approximation Theorem) | + | *Show that for any <math>{x\in\mathbb R}</math> and positive integer <math>{n}</math>, there exists a rational number <math>{\frac pq}</math> with <math>1\le q\le n</math> such that <math>\left|x-\frac pq\right|<\frac 1{nq}</math> (the classical Rational Approximation Theorem). |
Revision as of 12:07, 28 June 2006
Pigeonhole Principle
Also known as Dirichlet principle,
the basic pigeonhole principle says that if there are 
boxes, and more than 
objects, then one box MUST contain two or more objects. The extended version of the pigeonhole principle states that for n boxes, and more than 
objects, some box must contain at least 
objects. If you see a problem with the numbers , and 
, think about pigeonhole.
Examples
This page is in need of some relevant examples or practice problems. Help us out by adding some. Thanks.
- Show that in any group of five people, there are two who have an identical number of friends within the group. (Mathematical Circles)
- Seven line segments, with lengths no greater than 10 inches, and no shorter than 1 inch, are given. Show that one can choose three of them to represent the sides of a triangle. (Manhattan Mathematical Olympiad 2004)
- Prove that having 100 whole numbers, one can choose 15 of them so that the difference of any two is divisible by 7. (Manhattan Mathematical Olympiad 2005)
- Prove that from any set of one hundred whole numbers, one can choose either one number which is divisible by 100, or several numbers whose sum is divisible by 100. (Manhattan Mathematical Olympiad 2003)
- Prove that among any ten points located on a circle with diameter 5, there exist at least two at a distance less than 2 from each other.(Japan 1997)
- Show that for any
and positive integer 
, there exists a rational number 
with 
such that 
(the classical Rational Approximation Theorem).
and positive integer 
with 
such that 
(the classical Rational Approximation Theorem).
