View source for Pigeonhole Principle

In [[combinatorics]], the '''pigeonhole principle''' states that if <math>n+1</math> or more pigeons are placed into <math>n</math> holes, one hole must contain two or more pigeons. This seemingly trivial statement may be used with remarkable creativity to generate striking counting arguments; the principle bears particular fruit in Olympiad settings.

In older texts, the principle may be referred to as the '''Dirichlet box principle'''. A more useful phrasing of the problem through balls and boxes is that if <math>n</math> balls are to be placed in <math>k</math> boxes and <math>n>k</math>, then at least one box must contain more than one ball. 

== Proof == 
The pigeonhole principle may be demonstrated intuitively by the following argument: assume that there exists a way to place <math>n</math> balls into <math>k</math> boxes, where <math>n>k</math> such that all boxes contain at most one ball.

Let <math>b_1, b_2, \ldots, b_k</math> how many balls each box contains. Our condition that all boxes contain at most one ball implies that <math>b_r \leq 1</math> for all <math>1 \leq r \leq n</math>, so <cmath>b_1 + b_1 + \cdots + b_n \geq n.</cmath> However, we know that there are a total of <math>k</math> balls across all our boxes, so this sum must equal <math>k</math>: <cmath>b_1 + b_1 + \cdots + b_n = k.</cmath> Therefore, <math>k \geq n</math>. This contradicts our condition that <math>n>k</math>. Therefore, our assumption is incorrect; at least one box must contain two or more balls, as required. <math>\square</math>

In formal terms, the pigeonhole principle is a consequence of how we define one set to be larger than another set.

Let <math>N</math> be a set of <math>n</math> balls and <math>K</math> be a set of <math>k</math> boxes such that <math>n>k</math>, or <math>|N| > |K|</math>. The definition of this is that there exists a surjective mapping from <math>N</math> to <math>K</math>, but never a bijection. In other words, there exists a way to map every ball of <math>N</math> to every box of <math>K</math>, but not one that maps every ball to a distinct box. This is just a different way to phrase the fact that one box must contain more than one ball, which is the pigeonhole principle.

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

=== 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 inside 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]]