Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus
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"
(→‎Examples: solutions)
Line 5: Line 5:
  
 
== Examples ==
 
== Examples ==
−
 
 
{{problems}}
 
{{problems}}
 
=== Introductory Problems ===
 
=== Introductory Problems ===
  
 
=== Intermediate Problems ===
 
=== Intermediate Problems ===
−
# Show that in any group of five people, there are two who have an identical number of friends within the group. <div style="text-align:right">(Mathematical Circles)</div>
+
# Show that in any group of five 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?  
+
# 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]])
 
   
 
   
 
<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>
 
<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>
Line 18: Line 17:
  
 
=== Olympiad Problems ===
 
=== 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. <div style="text-align:right">(Manhattan Mathematical Olympiad 2004)</div>
+
# 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. ([[Pigeonhole Principle/Solutions#O1|Solution]]) <div style="text-align:right">(Manhattan Mathematical Olympiad 2004)</div>
−
# Prove that having 100 whole numbers, one can choose 15 of them so that the difference of any two is divisible by 7. <div style="text-align:right">(Manhattan Mathematical Olympiad 2005)</div>
+
# Prove that having 100 whole numbers, one can choose 15 of them so that the difference of any two is divisible by 7. ([[Pigeonhole Principle/Solutions#O2|Solution]]) <div style="text-align:right">(Manhattan Mathematical Olympiad 2005)</div>
−
# 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. <div style="text-align:right">(Manhattan Mathematical Olympiad 2003)</div>
+
# 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. ([[Pigeonhole Principle/Solutions#O3|Solution]]) <div style="text-align:right">(Manhattan Mathematical Olympiad 2003)</div>
−
# 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.<div style="text-align:right">(Japan 1997)</div>
+
# 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. ([[Pigeonhole Principle/Solutions#O4|Solution]]) <div style="text-align:right">(Japan 1997)</div>
−
# There are 51 senators in a senate.  The senate needs to be divided into <math>\displaystyle n</math> 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 <math>\displaystyle n</math> such that it is always possible to arrange the committees so that no senator hates another senator on his or her committee. <div style="text-align:right">(Red [[MOP]] lecture 2006)</div>
+
# There are 51 senators in a senate.  The senate needs to be divided into <math>\displaystyle n</math> 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 <math>\displaystyle n</math> such that it is always possible to arrange the committees so that no senator hates another senator on his or her committee. ([[Pigeonhole Principle/Solutions#O5|Solution]]) <div style="text-align:right">(Red [[MOP]] lecture 2006)</div>
−
# 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> <div style="text-align:right">(the classical Rational Approximation Theorem)</div>
+
# 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> ([[Pigeonhole Principle/Solutions#O6|Solution]]) <div style="text-align:right">(the classical Rational Approximation Theorem)</div>
 +
#Every point in a place 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. ([[Pigeonhole Principle/Solutions#O7|Solution]]) <div style="text-align:right">(USAMTS Year 18 - Round 1 - Problem 4)</div>
  
 
== See also ==
 
== See also ==
 
* [[Combinatorics]]
 
* [[Combinatorics]]

Revision as of 14:51, 29 January 2007

Also known as the Dirichlet box principle, the basic pigeonhole principle states that if there are $n$ boxes, and more than ${n}$ 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 ${nk}$ objects, some box must contain at least $k+1$ objects. Although this theorem seems obvious, many challenging olympiad problems can be solved by applying the pigeonhole principle.

Examples

This page is in need of some relevant examples or practice problems. Help us out by adding some. Thanks.

Introductory Problems

Intermediate Problems

  1. Show that in any group of five people, there are two who have an identical number of friends within the group. (Solution)
    (Mathematical Circles)
  2. 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)

$\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$

Olympiad Problems

  1. 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)
  2. 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)
  3. 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)
  4. 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)
  5. There are 51 senators in a senate. The senate needs to be divided into $\displaystyle n$ 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 $\displaystyle n$ 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)
  6. Show that for any ${x\in\mathbb R}$ and positive integer ${n}$, there exists a rational number ${\frac pq}$ with $1\le q\le n$ such that $\left|x-\frac pq\right|<\frac 1{nq}.$ (Solution)
    (the classical Rational Approximation Theorem)
  7. Every point in a place 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)

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Pigeonhole_Principle&oldid=12653"