Difference between revisions of "Pigeonhole Principle"

Revision as of 21:18, 25 October 2022

In combinatorics, the pigeonhole principle states that if $n+1$ or more pigeons are placed into $n$ holes, one hole must contain two or more pigeons. This seemingly trivial statement may be used with remarkable creativity to generate striking counting arguments, especially in Olympiad settings.

In older texts, the principle may be referred to as the Dirichlet box principle. A popular phrasing of the principle through balls and boxes is that if $n$ balls are to be placed in $k$ boxes and $n>k$ , 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 $n$ balls into $k$ boxes, where $n>k$ such that all boxes contain at most one ball.

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

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

Let $N$ be a set of $n$ balls and $K$ be a set of $k$ boxes such that $n>k$ (or equivalently, $|N| > |K|$ ). The definition of this is that there exists a surjective mapping from $N$ to $K$ , but not an injection. In other words, there exists a way to map every ball of $N$ to every box of $K$ , but it does not hold that if the boxes of two balls are the same, then the balls must be the same. That is to say, there must be two balls in the same box, 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? (Solution)
Suppose $S$ is a set of $n + 1$ integers. Prove that there exist distinct $a, b \in S$ such that $a - b$ is a multiple of $n$ . (Solution)

Intermediate Problems

Show that in any group of $n$ 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)
$\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$
(2006 AMC 10A Problems/Problem 20)
Show that for any irrational ${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)

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 inside 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 $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 $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)

@@ Line 1: / Line 1: @@
-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 [[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, especially 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.
+In older texts, the principle may be referred to as the '''Dirichlet box principle'''. A popular phrasing of the principle 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 ==
@@ Line 8: / Line 8: @@
 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.
+In formal terms, the pigeonhole principle is a consequence of how one set is ''defined'' 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.
+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 equivalently, <math>|N| > |K|</math>). The definition of this is that there exists a surjective mapping from <math>N</math> to <math>K</math>, but not an injection. In other words, there exists a way to map every ball of <math>N</math> to every box of <math>K</math>, but it does ''not'' hold that if the boxes of two balls are the same, then the balls must be the same. That is to say, there must be two balls in the same box, which is the pigeonhole principle.
 == Examples ==

Page

Toolbox

Search