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"
(→Examples) |
(fixed numbering) |
||
| Line 8: | Line 8: | ||
=== Introductory Problems === | === Introductory Problems === | ||
| − | + | #If a Martian has an infinite number of red, blue, yellow, and black socks in a drawer, how many socks must the Martian pull out of the drawer to guarantee he has a pair? ([[Pigeonhole Principle/Solutions#M1|Solution]]) | |
| − | + | #Suppose <math>S</math> is a set of <math>n + 1</math> integers. Prove that there exist distinct <math>a, b \in S</math> such that <math>a - b</math> is a multiple of <math>n</math>. ([[Pigeonhole Principle/Solutions#M1|Solution]]) | |
| − | |||
=== Intermediate Problems === | === Intermediate Problems === | ||
| − | + | #Show that in any group of <math>n</math> people, there are two who have an identical number of friends within the group. ([[Pigeonhole Principle/Solutions#M1|Solution]]) <div style="text-align:right">(Mathematical Circles)</div> | |
| − | + | #Six distinct positive integers are randomly chosen between 1 and 2006, inclusive. What is the probability that some pair of these integers has a difference that is a multiple of 5? ([[Pigeonhole Principle/Solutions#M2|Solution]])<div style="text-align:center"><math>\mathrm{(A) \ } \frac{1}{2}\qquad\mathrm{(B) \ } \frac{3}{5}\qquad\mathrm{(C) \ } \frac{2}{3}\qquad\mathrm{(D) \ } \frac{4}{5}\qquad\mathrm{(E) \ } 1\qquad</math></div><div style="text-align:right">([[2006 AMC 10A Problems/Problem 20]])</div> | |
| − | + | #Show that for any irrational <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> ([[Pigeonhole Principle/Solutions#O7|Solution]]) <div style="text-align:right">(the classical Rational Approximation Theorem)</div> | |
| − | |||
| − | |||
| − | <div style="text-align:right">([[2006 AMC 10A Problems/Problem 20]])</div> | ||
| − | |||
| − | |||
| − | |||
=== Olympiad Problems === | === Olympiad Problems === | ||
Revision as of 16:34, 1 June 2011
The Pigeonhole Principle (also known as the Dirichlet box principle, Dirichlet principle or box principle) states that if 
or more pigeons are placed in 
holes, then one hole must contain two or more pigeons.
Although this theorem seems obvious, many challenging olympiad problems can be solved by applying the Pigeonhole Principle. Often, a clever choice of box is necessary.
The extended version of the Pigeonhole Principle states that if 
objects are placed in boxes then at least one box must hold at least 
objects. Here 
denotes the ceiling function.
Contents
Examples
Introductory Problems
- If a Martian has an infinite number of red, blue, yellow, and black socks in a drawer, how many socks must the Martian pull out of the drawer to guarantee he has a pair? (Solution)
- Suppose
is a set of 
integers. Prove that there exist distinct 
such that 
is a multiple of 
. (Solution)
is a set of 
such that 
is a multiple of Intermediate Problems
- Show that in any group of people, there are two who have an identical number of friends within the group. (Solution) (Mathematical Circles)
- Six distinct positive integers are randomly chosen between 1 and 2006, inclusive. What is the probability that some pair of these integers has a difference that is a multiple of 5? (Solution)
- Show that for any irrational
and positive integer 
, there exists a rational number 
with 
such that 
(Solution) (the classical Rational Approximation Theorem)
and positive integer 
, there exists a rational number 
with 
such that 
(Olympiad Problems
- 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. (Solution) (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. (Solution) (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. (Solution) (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. (Solution) (Japan 1997)
- Every point in a plane is either red, green, or blue. Prove that there exists a rectangle in the plane such that all of its vertices are the same color. (Solution) (USAMTS Year 18 - Round 1 - Problem 4)
- There are 51 senators in a senate. The senate needs to be divided into committees such that each senator is on exactly one committee. Each senator hates exactly three other senators. (If senator A hates senator B, then senator B does 'not' necessarily hate senator A.) Find the smallest such that it is always possible to arrange the committees so that no senator hates another senator on his or her committee. (Solution) (Red MOP lecture 2006)
