View source for Pigeonhole Principle

The '''Pigeonhole Principle''' (also known as the ''[[Dirichlet]] box principle'', ''Dirichlet principle'' or ''box principle'') states that if <math>n + 1</math> or more pigeons are placed in <math>n</math> 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 <math>k</math> objects are placed in <math>n</math> boxes then at least one box must hold at least <math>\left\lceil \frac{n}{k} \right\rceil</math> objects.  Here <math>\lceil \cdot \rceil</math> denotes the [[ceiling function]].

== Examples ==
=== Introductory Problems ===

1. 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]])

2. 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 ===
1. 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> 


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? ([[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>


3. 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#O7|Solution]]) <div style="text-align:right">(the classical Rational Approximation Theorem)</div>

=== 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. ([[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. ([[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. ([[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. ([[Pigeonhole Principle/Solutions#O4|Solution]]) <div style="text-align:right">(Japan 1997)</div>
#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. ([[Pigeonhole Principle/Solutions#O5|Solution]]) <div style="text-align:right">(USAMTS Year 18 - Round 1 - Problem 4)</div>
# There are 51 senators in a senate.  The senate needs to be divided into <math>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>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#O6|Solution]]) <div style="text-align:right">(Red [[MOP]] lecture 2006)</div>

== See also ==
* [[Combinatorics]]


[[Category:Combinatorics]]