Difference between revisions of "Pigeonhole Principle"

Latest revision as of 18:13, 19 June 2024

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 common phrasing of the principle uses balls and boxes and 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

An intuitive proof of the pigeonhole principle is as follows: suppose for contradiction 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 definition that $n>k$ . Therefore, our assumption must be incorrect; at least one box must contain two or more balls. $\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$ . The definition that $|N| > |K|$ (as in our problem) 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 or more balls in the same box—which is the pigeonhole principle.

Introductory Examples

Example 1

If a Martian has an infinite number of red, blue, yellow, and black socks in a drawer, what is the minimum number of socks that the Martian must pull out of the drawer to guarantee they have a pair?

Solution: Intuitively, you might realize that after we select four socks of different colors (one red, one blue, one yellow, and one black), the Martian can't select a fifth sock without creating a pair. We may use this to prove the problem:

Note that the Martian may select $4$ socks without a pair: one red, one blue, one yellow, and one black sock. However, if the Martian selects $5$ socks from $4$ colors, the pigeonhole principle guarantees that $2$ socks must have the same color (where the $5$ socks are "pigeons" and the $4$ colors are "holes"). Therefore, $5$ is the minimum number of socks they must draw to guarantee a pair. $\square$

Example 2

Let $S = {1, 2, 3, \ldots, 2n}$ . Show that if we choose $n+1$ numbers from $S$ , then there exist two numbers such that one is a multiple of the other.

Solution:

We write each number as $2^ab$ for some integers $a$ and $b$ , where $a$ is nonnegative and $b$ is odd ( $b$ can also be $1$ ). Because we select $n+1$ integers and there are $n$ possible values of $b$ , Pigeonhole Principle guarantees that two numbers will share the same $b$ value. These numbers are multiples—if we define the two numbers $2^ib$ and $2^jb$ where $i>j$ , we may multiply $2^jb$ by $2^{i-j}$ to get $2^ib$ , as desired. $\square$

Example 3

Suppose $S$ is a set of $n + 1$ integers. Prove that there exists distinct $a, b$ in $S$ such that $a - b$ is a multiple of $n$ .

Solution: Note that for any such $a$ and $b$ , $n | (a - b).$ We may rewrite this in modular arithmetic as $a - b \equiv 0 \textrm{ } (\textrm{mod }n)$ , or $a \equiv b \textrm{ } (\textrm{mod }n).$ Therefore, we wish to show that there exist $a$ and $b$ with the same remainder modulo n. Note that there are $n+1$ integers in $S$ and $n$ possible remainders (namely, $0, 1, \ldots, n-1$ ) modulo $n$ . Then by the pigeonhole principle, there exist two integers with the same remainder modulo $n$ . As shown earlier, this implies that their difference is a multiple of $n$ , as required. $\square$

Example 4

Show that in any group of $n$ people, there are two who have an identical number of friends within the group.

Solution: Note that for any person from the group, the minimum number of in-group friends they can have is $0$ (nobody) and the maximum is $n-1$ (everybody but themselves). Hence, there are $n$ possible values for an individual's number of in-group friends.

However, note that if a person has $0$ in-group friends, nobody else can be friends with all other $n-1$ individuals; vice-versa if an individual has $n-1$ friends. There cannot exist two individuals with $0$ and $n-1$ friends. Therefore, there are only $n-1$ possible values of an individual's number of in-group friends.

Then because there are $n$ individuals and $n-1$ possible values of in-group friends, the Pigeonhole Principle guarantees that two individuals have the same number of friends within the group. $\square$

Intermediate Examples

Example 1: Rational Approximation Theorem

Show that for any irrational number $x$ and positive integer $n$ , there exists a rational number $\frac{p}{q}$ with $1 \leq q \leq n$ such that $|x - \frac{p}{q}| < \frac{1}{nq}$ .

Solution: Take a moment to digest the question; in short, our task is to prove the existence of a rational number close to our irrational $x$ . In particular, $n$ is almost like a "confidence level"—where a higher $n$ increases the denominator $q$ and decreases the distance between $x$ and $\frac{p}{q}$ .

To simplify the problem, we multiply both sides of the inequality by $q$ to get $|qx-p| < \frac{1}{n}.$ Note that we wish $|qx-p|$ to be less than one; hence, we might think to define $p$ such that $qx-p$ is $\{ qx \}$ , the fractional part of $qx$ . In formal terms, we let $p=\lfloor qx \rfloor$ such that $|qx-p|=|qx-\lfloor qx \rfloor|=|\{ qx\} |=\{ qx\}$ .

Now, we wish to demonstrate that out of $\{ x \}, \{ 2x \}, \ldots, \{ nx \}$ , there exists a positive integer $q$ such that $\{ qx \}$ lies in the interval $[0,1/n)$ . We can view the intervals $[0, 1/n), [1/n,2/n), \ldots, [(n-1)/n, 1)$ as windows that contain all our multiples of $\{ qx \}$ . Note that if $[0, 1/n)$ and $[(n-1)/n, 1)$ contain a multiple, then we are done.

Suppose every interval is filled; then one value of $\{ qx \}$ must lie in $[0, 1/n)$ . If there exists an interval that is not filled, we have at most $n-1$ filled intervals and $n$ multiples. The Pigeonhole Principle thus guarantees that there exists an interval with two values of $\{ qx \}$ . Letting these values be $q_1$ and $q_2$ , we note that $\{ (q_1 - q_2)x \}$ is either in the first or last interval. Hence, in either case, there exists a $q$ such that $\{ qx \}$ lies in $[0, 1/n)$ , which is the theorem. We may assemble this into a formal proof:

Proof: Let $k$ be an integer from $0$ to $n$ inclusive. Note that for all of $0x, 1x, \ldots, nx$ , we can write $kx = a_k + b_k$ , where $a_k$ is an integer and $0 \leq b_k < 1$ .

Consider the $n$ intervals from $[0, 1)$ of size $\frac{1}{n}$ . We have $n+1$ total $b_0, b_1, \ldots b_n$ ; hence, the Pigeonhole Principle guarantees the existence of some $i$ and $j$ such that $b_i$ and $b_j$ are in the same interval. Without loss of generality, let $i>j$ . Then $|b_i - b_j| < \frac{1}{n}$ .

We have that $|(i-j)x - (a_i - a_j)| = |(ix-a_i) - (jx-a_j)| = |b_i - b_j| < \frac{1}{n}.$ Note that the fact $i-j>0$ allows us to divide both sides of this inequality by $i - j$ to obtain $|x-\frac{a_i - a_j}{i - j}| < \frac{1}{n(i - j)}.$ Therefore, $\frac{a_i - a_j}{i - j}$ is a rational $\frac{p}{q}$ such that $|x-\frac{p}{q}| < \frac{1}{nq}$ , which completes the proof. $\square$

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: @@
-=== 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, especially in Olympiad settings.
-The basic pigeonhole principle says that if there are <math>n</math> holes, and <math>n+k</math> pigons (k>1), then one hole MUST contain two or more pigeons. The extended version of the pigeonhole principle states that for n holes, and <math>{nk+j}</math> pigeons, j>1, some hole must contain k+1 pigeons. If you see a problem with the numbers n, and nk+1, think about pigeonhole.
+In older texts, the principle may be referred to as the '''Dirichlet box principle'''. A common phrasing of the principle uses balls and boxes and 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.
-=== Examples ===
+== Proof ==
+An intuitive proof of the pigeonhole principle is as follows: suppose for contradiction 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.
-Can users find some?
+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 definition that <math>n>k</math>. Therefore, our assumption must be incorrect; at least one box must contain two or more balls. <math>\square</math>
-You could paste in [http://www.upal.ca/adeel/problems/2006/4/9.pdf these]... (maybe, just a suggestion)
+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>. The definition that <math>|N| > |K|</math> (as in our problem) 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 or more balls in the same box—which is the pigeonhole principle.
+== Introductory Examples ==
+=== Example 1 ===
+''If a Martian has an infinite number of red, blue, yellow, and black socks in a drawer, what is the minimum number of socks that the Martian must pull out of the drawer to guarantee they have a pair?''
+'''Solution''': Intuitively, you might realize that after we select four socks of different colors (one red, one blue, one yellow, and one black), the Martian can't select a fifth sock without creating a pair. We may use this to prove the problem:
+Note that the Martian may select <math>4</math> socks without a pair: one red, one blue, one yellow, and one black sock. However, if the Martian selects <math>5</math> socks from <math>4</math> colors, the pigeonhole principle guarantees that <math>2</math> socks must have the same color (where the <math>5</math> socks are "pigeons" and the <math>4</math> colors are "holes"). Therefore, <math>5</math> is the minimum number of socks they must draw to guarantee a pair. <math>\square</math>
+=== Example 2 ===
+''Let <math>S = {1, 2, 3, \ldots, 2n}</math>. Show that if we choose <math>n+1</math> numbers from <math>S</math>, then there exist two numbers such that one is a multiple of the other.
+'''Solution''':
+We write each number as <math>2^ab</math> for some integers <math>a</math> and <math>b</math>, where <math>a</math> is nonnegative and <math>b</math> is odd (<math>b</math> can also be <math>1</math>). Because we select <math>n+1</math> integers and there are <math>n</math> possible values of <math>b</math>, Pigeonhole Principle guarantees that two numbers will share the same <math>b</math> value. These numbers are multiples—if we define the two numbers <math>2^ib</math> and <math>2^jb</math> where <math>i>j</math>, we may multiply <math>2^jb</math> by <math>2^{i-j}</math> to get <math>2^ib</math>, as desired. <math>\square</math>
+=== Example 3 ===
+''Suppose <math>S</math> is a set of <math>n + 1</math> integers. Prove that there exists distinct <math>a, b</math> in <math>S</math> such that <math>a - b</math> is a multiple of <math>n</math>.''
+'''Solution''': Note that for any such <math>a</math> and <math>b</math>, <cmath>n | (a - b).</cmath> We may rewrite this in [[modular arithmetic]] as <math> a - b \equiv 0 \textrm{ } (\textrm{mod }n)</math>, or <cmath>a \equiv b \textrm{ } (\textrm{mod }n).</cmath> Therefore, we wish to show that there exist <math>a</math> and <math>b</math> with the same remainder modulo n. Note that there are <math>n+1</math> integers in <math>S</math> and <math>n</math> possible remainders (namely, <math>0, 1, \ldots, n-1</math>) modulo <math>n</math>. Then by the pigeonhole principle, there exist two integers with the same remainder modulo <math>n</math>. As shown earlier, this implies that their difference is a multiple of <math>n</math>, as required. <math>\square</math>
+=== Example 4 ===
+''Show that in any group of <math>n</math> people, there are two who have an identical number of friends within the group.''
+'''Solution''': Note that for any person from the group, the minimum number of in-group friends they can have is <math>0</math> (nobody) and the maximum is <math>n-1</math> (everybody but themselves). Hence, there are <math>n</math> possible values for an individual's number of in-group friends.
+However, note that if a person has <math>0</math> in-group friends, nobody else can be friends with all other <math>n-1</math> individuals; vice-versa if an individual has <math>n-1</math> friends. ''There cannot exist two individuals with <math>0</math> and <math>n-1</math> friends''. Therefore, there are only <math>n-1</math> possible values of an individual's number of in-group friends.
+Then because there are <math>n</math> individuals and <math>n-1</math> possible values of in-group friends, the Pigeonhole Principle guarantees that two individuals have the same number of friends within the group. <math>\square</math>
+== Intermediate Examples ==
+=== Example 1: Rational Approximation Theorem ===
+''Show that for any irrational number <math>x</math> and positive integer <math>n</math>, there exists a rational number <math>\frac{p}{q}</math> with <math>1 \leq q \leq n</math> such that <math>|x - \frac{p}{q}| < \frac{1}{nq}</math>.''
+'''Solution''': Take a moment to digest the question; in short, our task is to ''prove the existence of a rational number'' close to our irrational <math>x</math>. In particular, <math>n</math> is almost like a "confidence level"—where a higher <math>n</math> increases the denominator <math>q</math> and decreases the distance between <math>x</math> and <math>\frac{p}{q}</math>.
+To simplify the problem, we multiply both sides of the inequality by <math>q</math> to get <cmath>|qx-p| < \frac{1}{n}.</cmath> Note that we wish <math>|qx-p|</math> to be less than one; hence, we might think to define <math>p</math> such that <math>qx-p</math> is <math>\{ qx \}</math>, the fractional part of <math>qx</math>. In formal terms, we let <math>p=\lfloor qx \rfloor</math> such that <math>|qx-p|=|qx-\lfloor qx \rfloor|=|\{ qx\} |=\{ qx\}</math>.
+Now, we wish to demonstrate that out of <math>\{ x \}, \{ 2x \}, \ldots, \{ nx \}</math>, there exists a positive integer <math>q</math> such that <math>\{ qx \}</math> lies in the interval <math>[0,1/n)</math>. We can view the intervals <math>[0, 1/n), [1/n,2/n), \ldots, [(n-1)/n, 1)</math> as windows that contain all our multiples of <math>\{ qx \}</math>. Note that if <math>[0, 1/n)</math> and <math>[(n-1)/n, 1)</math> contain a multiple, then we are done.
+Suppose every interval is filled; then one value of <math>\{ qx \}</math> must lie in <math>[0, 1/n)</math>. If there exists an interval that is not filled, we have at most <math>n-1</math> filled intervals and <math>n</math> multiples. The Pigeonhole Principle thus guarantees that there exists an interval with two values of <math>\{ qx \}</math>. Letting these values be <math>q_1</math> and <math>q_2</math>, we note that <math>\{ (q_1 - q_2)x \}</math> is either in the first or last interval. Hence, in either case, there exists a <math>q</math> such that <math>\{ qx \}</math> lies in <math>[0, 1/n)</math>, which is the theorem. We may assemble this into a formal proof:
+'''Proof''': Let <math>k</math> be an integer from <math>0</math> to <math>n</math> inclusive. Note that for all of <math>0x, 1x, \ldots, nx</math>, we can write <math>kx = a_k + b_k</math>, where <math>a_k</math> is an integer and <math>0 \leq b_k < 1</math>.
+Consider the <math>n</math> intervals from <math>[0, 1)</math> of size <math>\frac{1}{n}</math>. We have <math>n+1</math> total <math>b_0, b_1, \ldots b_n</math>; hence, the Pigeonhole Principle guarantees the existence of some <math>i</math> and <math>j</math> such that <math>b_i</math> and <math>b_j</math> are in the same interval. Without loss of generality, let <math>i>j</math>. Then <math>|b_i - b_j| < \frac{1}{n}</math>.
+We have that <cmath>|(i-j)x - (a_i - a_j)| = |(ix-a_i) - (jx-a_j)| = |b_i - b_j| < \frac{1}{n}.</cmath> Note that the fact <math>i-j>0</math> allows us to divide both sides of this inequality by <math>i - j</math> to obtain <cmath>|x-\frac{a_i - a_j}{i - j}| < \frac{1}{n(i - j)}.</cmath> Therefore, <math>\frac{a_i - a_j}{i - j}</math> is a rational <math>\frac{p}{q}</math> such that <math>|x-\frac{p}{q}| < \frac{1}{nq}</math>, which completes the proof. <math>\square</math>
+== 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]] [[Category:Definition]]

Page

Toolbox

Search