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

Difference between revisions of "Pigeonhole Principle/Solutions"

(→‎M3)
(→‎O4)
 
(30 intermediate revisions by 9 users not shown)
Line 13: Line 13:
 
==Intermediate==
 
==Intermediate==
 
===M1===
 
===M1===
−
The maximum number of friends one person in the group can have is 4, and the minimum is 0. If all of the members have at least one friend, then each individual can have somewhere between <math>1</math> to <math>4</math> friends; as there are <math>5</math> individuals, by pigeonhole there must be at least two with the same number of friends. If one individual has no friends, then we can repeat the above argument for the remaining 4 individuals, and if more than one individual has no friends then we are done.
+
The maximum number of friends one person in the group can have is n-1, and the minimum is 0. If all of the members have at least one friend, then each individual can have somewhere between <math>1</math> to <math>n-1</math> friends; as there are <math>n</math> individuals, by pigeonhole there must be at least two with the same number of friends. If one individual has no friends, then the remaining friends must have from <math>1</math> to <math>n-2</math> friends for the remaining friends not to also have no friends. By pigeonhole again, this leaves at least <math>1</math> other person with <math>0</math> friends.
  
 
===M2===
 
===M2===
Line 23: Line 23:
 
Now, we wish to find a <math>q</math> between 1 and <math>n</math> such that <math>xq</math> is within <math>\frac{1}{n}</math> of some integer.
 
Now, we wish to find a <math>q</math> between 1 and <math>n</math> such that <math>xq</math> is within <math>\frac{1}{n}</math> of some integer.
 
Let <math>\{a\}</math> denote the fractional part of <math>a</math>.
 
Let <math>\{a\}</math> denote the fractional part of <math>a</math>.
−
Now, we sort the pigeons <math>\{x\}, \{2x\}, \hdots, \{nx\}</math> into the holes <math>(0, 1/n}), (1/n, 2/n), \hdots, ((n - 1)/n, 1).</math>
+
Now, we sort the pigeons <math>\{x\}, \{2x\}, \hdots, \{nx\}</math> into the holes <math>(0, 1/n)), (1/n, 2/n), \hdots, ((n - 1)/n, 1).</math>
−
If any pigeon falls into the first hole, we are done.
+
If any pigeon falls into the first or last hole, we are done.
−
Therefore assume otherwise; then some two pigeons <math>\{ix\}, \{jx\} \in (k/n, (k + 1)/n)</math> for <math>1 \le k < n</math>.
+
Therefore assume otherwise; then some two pigeons <math>\{ix\}, \{jx\} \in (k/n, (k + 1)/n)</math> for <math>1 \le k < n - 1</math>.
 
Assume, without loss of generality, that <math>j - i > 0</math>.
 
Assume, without loss of generality, that <math>j - i > 0</math>.
 
Then we have that <math>\{(j - i)x\}</math> must fall into the first or last hole, contradiction.
 
Then we have that <math>\{(j - i)x\}</math> must fall into the first or last hole, contradiction.
Line 31: Line 31:
 
==Olympiad==
 
==Olympiad==
 
===O1===
 
===O1===
−
By the [[Triangle Inequality]] Theorem, a side of a triangle can be less than the sum of the other two sides. Assume that the first two segments are as short as possible (1&nbsp;inch). For a triangle to not exist, the next term must be 2, then 3, 5, 8, and 13 (this is the [[Fibonacci number|Fibonacci sequence]]). The 7th term is 13, which is greater than 10 inches.<!--Where does pigeonhole come in-->
+
By the [[Triangle Inequality]] Theorem, a side of a triangle must be less than the sum of the other two sides. This is equivalent to say that every side must be greater than the subtraction of the other two sides.
 +
 
 +
Consider the following statements:
 +
 
 +
1. If we have 2 line segments of lengths <math>a,b</math> (so that <math>a \geq b</math> and <math>a - b < 1</math>); then if we have at least a line segment of length <math>c</math> left to check (so that <math>b \geq c</math> ), we will get that <math>a, b</math> and <math>c</math> are sides of a triangle. This is true because <math>c \geq 1</math>. This means if we check, for example,  <math>5.5</math> and <math>5</math> then any number less than or equal to <math>5</math> will satisfy the condition of them being sides of a triangle.
 +
 
 +
2. If we have 3 line segments of lengths <math>a,b,c</math> to check inside an interval with a form <math>[k,2k[</math>, so that <math>k \geq 1</math> we will find that they are sides of a triangle. This is true because <math>|a - b| < k</math>, <math>|a - c| < k</math>, <math>|b - c| < k</math> and <math>a \geq b \geq c \geq k</math>.
 +
 
 +
3.  If we have 2 line segments of lengths <math>a,b</math> so that <math>a \geq b</math>, then <math>a,b,c</math> are sides of a triangle if <math>b \geq c</math> and <math> c > a  - b</math>. This is a generalization of 1.
 +
 
 +
Now let's consider the intervals <math>[1,2[</math> , <math>[2,4[</math> and <math>[4,10]</math>.
 +
 
 +
If we have 3 lines segment of lengths <math>a,b,c \in [1,2[</math>, then they are sides of a triangle because of 2.
 +
 
 +
If we have 3 lines segment of lengths <math>a,b,c \in [2,4[</math>, then they are sides of a triangle because of 2.
 +
 
 +
To analyze the case of having 3 lines segment of lengths <math>a,b,c \in [4,10]</math>, we can have two subcases. In both of them we will assume that 2 line segments' lengths are in <math>[1,2[</math> and 2 line segments' lengths are in <math>[2,4[</math> (otherwise it wouldn't be necessary to check because we would have 3 lenghts in the same interval). Also, that the difference between the two lengths in <math>[2,4[</math> is greater than or equal to 1. (So that we can't apply 1.)
 +
 
 +
A. If we can find <math>a,b \in [4,10]</math> so that <math>|a - b| < 3</math>, we are done because there is a <math>c \in [2,4[</math> so that <math>c \geq 3</math> (Using 3. and the assumptions)
 +
B. If we can't find <math>a,b \in [4,10]</math> so that <math>|a - b| < 3</math>, that means the lengths are <math>4,7,10</math>. But if we look at them, they are 3 sides of a triangle.
 +
 
 +
Finally, as we wish to distribute 7 lengths in 3 intervals, the Pigeonhole Principle can be used to guarantee that at least 3 line segments' lengths belong to a same interval, and therefore to satisfy the condition.
 +
 
 
===O2===
 
===O2===
 
For the difference to be a multiple of 7, the integers must have equal [[Modular arithmetic/Introduction |modulo]] 7 residues. To avoid having 15 with the same residue, 14 numbers with different modulo 7 residues can be picked (<math>14 * 7 = 98</math>). Thus, two numbers are left over and have to share a modulo 7 residue with the other numbers under the pigeonhole principle.
 
For the difference to be a multiple of 7, the integers must have equal [[Modular arithmetic/Introduction |modulo]] 7 residues. To avoid having 15 with the same residue, 14 numbers with different modulo 7 residues can be picked (<math>14 * 7 = 98</math>). Thus, two numbers are left over and have to share a modulo 7 residue with the other numbers under the pigeonhole principle.
 +
 
===O3===
 
===O3===
−
See [http://www.artofproblemsolving.com./Resources/AoPS_R_A_HowWriteName.php this article].
+
Label the numbers in the set <math>x_1,\dots,x_{100}</math>, consider the 100 subsets <math>\{x_1\}, \{x_1,x_2\},\dots,\{x_1,\dots,x_{100}\}</math> and for each of these subsets, compute its sum. If none of these sums are divisible by <math>100</math>, then there are <math>100</math> sums and <math>99</math> residue classes mod <math>100</math> (excluding <math>0</math>). Therefore two of these sums are the same mod <math>100</math>, say <math>x_1+\cdots+x_i\equiv x_1+\cdots+x_j\pmod{100}</math> (with <math>i<j</math>). Then <math>x_{i+1}+\cdots+x_j\equiv 0\pmod{100}</math>, and the subset <math>\{x_{i+1},\dots,x_j\}</math> suffices.
 +
 
 
===O4===
 
===O4===
−
Inscribe a regular <math>9</math>-gon, it will divide the circle into <math>9</math> equal arcs. The length of the side of this <math>9</math>-gon is <math>\simeq 1.71</math>, and this is an upper bound on the distance of any two points on the arc. From the pigeonhole principle one of the arcs contains at least two of the points.
+
We can split up the circle into nine parts as shown below, where the smaller circle in the middle has a diameter of <math>2</math>.
 +
 
 +
<asy>
 +
draw(circle((0, 0), 1));
 +
draw(circle((0, 0), 0.4));
 +
draw(0.4*dir(0)--dir(0));
 +
draw(0.4*dir(45)--dir(45));
 +
draw(0.4*dir(90)--dir(90));
 +
draw(0.4*dir(135)--dir(135));
 +
draw(0.4*dir(180)--dir(180));
 +
draw(0.4*dir(225)--dir(225));
 +
draw(0.4*dir(270)--dir(270));
 +
draw(0.4*dir(315)--dir(315));
 +
</asy>
 +
 
 +
By the pigeonhole principle, at least one of these parts must contain <math>2</math> or more points. Any two points within the smallest circle must have a distance of less than <math>2</math>. For each of the <math>8</math> outer regions, the maximum distance between <math>2</math> points within the same region will be when the two points are on opposing corners, or when they are placed on the two outer corners.
 +
 
 +
First, we determine which of these lengths is longer. The segment shown in blue below has length <math>\frac{5\sqrt{2}}{4}</math>. Using <math>\sqrt{2}\approx 1.414</math> to approximate this value, we get <math>\frac{7.07}{4} = 1.7675</math>. This value is slightly above <math>1.75</math>, which means it is closer to <math>A</math> than <math>B</math>. Therefore, <math>BC</math> is longer than <math>AC</math> so we only need to verify that the length of <math>BC</math> is less than <math>2</math>.
 +
 
 +
<asy>
 +
draw(circle((0, 0), 1));
 +
draw(circle((0, 0), 0.4));
 +
draw(0.4*dir(0)--dir(0));
 +
draw(0.4*dir(45)--dir(45));
 +
draw(0.4*dir(90)--dir(90));
 +
draw(0.4*dir(135)--dir(135));
 +
draw(0.4*dir(180)--dir(180));
 +
draw(0.4*dir(225)--dir(225));
 +
draw(0.4*dir(270)--dir(270));
 +
draw(0.4*dir(315)--dir(315));
 +
 
 +
draw(dir(90)--dir(45), dashed);
 +
draw(dir(45)--(1/sqrt(2), 0), blue);
 +
draw(0.4*dir(90)--dir(45), red);
 +
 
 +
dot("$A$", dir(90), N);
 +
dot("$B$", 0.4*dir(90), NW);
 +
dot("$C$", dir(45), NE);
 +
</asy>
 +
 
 +
This distance is equal to the hypotenuse of a right triangle with legs of length <math>\frac{\sqrt{2}}{2}</math> and <math>\frac{5-\sqrt{2}}{2}</math>, as shown below.
 +
 
 +
<asy>
 +
draw(circle((0, 0), 1));
 +
draw(circle((0, 0), 0.4));
 +
draw(0.4*dir(45)--dir(45));
 +
draw(0.4*dir(90)--dir(90));
 +
draw(0.4*dir(135)--dir(135));
 +
draw(0.4*dir(180)--dir(180));
 +
draw(0.4*dir(225)--dir(225));
 +
draw(0.4*dir(270)--dir(270));
 +
draw(0.4*dir(315)--dir(315));
 +
 
 +
draw(0.4*dir(45)--(0.4/sqrt(2), 0), dotted);
 +
draw((0.4/sqrt(2), 0)--dir(0), dotted);
 +
draw(0.4*dir(45)--dir(0), red);
 +
</asy>
 +
 
 +
After using the pythagorean theorem, we find the red line above has length <math>\frac{\sqrt{29-10\sqrt2}}{2}</math>. Approximating this value using <math>\sqrt{2}\approx 1.414</math>, we get <math>\frac{\sqrt{29-14.14}}{2}=\frac{\sqrt{15.86}}{2}<\frac{4}{2}=2</math>.
 +
 
 +
Therefore, no two points within the same region can have a distance of <math>2</math> or more. As stated earlier, at least one of these regions must have <math>2</math> or more points, so there must be a pair of points with a distance of less than <math>2</math>.
  
 
===O5===
 
===O5===
 
The pigeonhole principle is used in [http://usamts.org/Solutions/Solution4_1_18.pdf these solutions (PDF)].
 
The pigeonhole principle is used in [http://usamts.org/Solutions/Solution4_1_18.pdf these solutions (PDF)].
 
===O6===
 
===O6===
−
{{solution}}
+
In the worst case, consider that senator <math>S</math> hates a set of 3 senators, while he himself is hated by a completely different set of 3 other senators. Thus, given one senator, there may be a maximum of 6 other senators whom he cannot work with. If we have a minimum of 7 committees, there should be at least one committee suitable for the senator <math>S</math> after the assignment of the 6 conflicting senators.
 
<!--todo-->
 
<!--todo-->

Latest revision as of 00:34, 26 October 2021

These are the solutions to the problems related to the Pigeonhole Principle.

Introductory

I1

The Martian must pull 5 socks out of the drawer to guarantee he has a pair. In this case the pigeons are the socks he pulls out and the holes are the colors. Thus, if he pulls out 5 socks, the Pigeonhole Principle states that some two of them have the same color. Also, note that it is possible to pull out 4 socks without obtaining a pair.

I2

Consider the residues of the elements of $S$, modulo $n$. By the Pigeonhole Principle, there exist distinct $a, b \in S$ such that $a \equiv b \pmod n$, as desired.

Intermediate

M1

The maximum number of friends one person in the group can have is n-1, and the minimum is 0. If all of the members have at least one friend, then each individual can have somewhere between $1$ to $n-1$ friends; as there are $n$ individuals, by pigeonhole there must be at least two with the same number of friends. If one individual has no friends, then the remaining friends must have from $1$ to $n-2$ friends for the remaining friends not to also have no friends. By pigeonhole again, this leaves at least $1$ other person with $0$ friends.

M2

For the difference to be a multiple of 5, the two integers must have the same remainder when divided by 5. Since there are 5 possible remainders (0-4), by the pigeonhole principle, at least two of the integers must share the same remainder. Thus, the answer is 1 (E).

M3

Multiplying both sides by $q$, we have \[|xq - p| < \frac{1}{n}.\] Now, we wish to find a $q$ between 1 and $n$ such that $xq$ is within $\frac{1}{n}$ of some integer. Let $\{a\}$ denote the fractional part of $a$. Now, we sort the pigeons $\{x\}, \{2x\}, \hdots, \{nx\}$ into the holes $(0, 1/n)), (1/n, 2/n), \hdots, ((n - 1)/n, 1).$ If any pigeon falls into the first or last hole, we are done. Therefore assume otherwise; then some two pigeons $\{ix\}, \{jx\} \in (k/n, (k + 1)/n)$ for $1 \le k < n - 1$. Assume, without loss of generality, that $j - i > 0$. Then we have that $\{(j - i)x\}$ must fall into the first or last hole, contradiction.

Olympiad

O1

By the Triangle Inequality Theorem, a side of a triangle must be less than the sum of the other two sides. This is equivalent to say that every side must be greater than the subtraction of the other two sides.

Consider the following statements:

1. If we have 2 line segments of lengths $a,b$ (so that $a \geq b$ and $a - b < 1$); then if we have at least a line segment of length $c$ left to check (so that $b \geq c$ ), we will get that $a, b$ and $c$ are sides of a triangle. This is true because $c \geq 1$. This means if we check, for example, $5.5$ and $5$ then any number less than or equal to $5$ will satisfy the condition of them being sides of a triangle.

2. If we have 3 line segments of lengths $a,b,c$ to check inside an interval with a form $[k,2k[$, so that $k \geq 1$ we will find that they are sides of a triangle. This is true because $|a - b| < k$, $|a - c| < k$, $|b - c| < k$ and $a \geq b \geq c \geq k$.

3. If we have 2 line segments of lengths $a,b$ so that $a \geq b$, then $a,b,c$ are sides of a triangle if $b \geq c$ and $c > a - b$. This is a generalization of 1.

Now let's consider the intervals $[1,2[$ , $[2,4[$ and $[4,10]$.

If we have 3 lines segment of lengths $a,b,c \in [1,2[$, then they are sides of a triangle because of 2.

If we have 3 lines segment of lengths $a,b,c \in [2,4[$, then they are sides of a triangle because of 2.

To analyze the case of having 3 lines segment of lengths $a,b,c \in [4,10]$, we can have two subcases. In both of them we will assume that 2 line segments' lengths are in $[1,2[$ and 2 line segments' lengths are in $[2,4[$ (otherwise it wouldn't be necessary to check because we would have 3 lenghts in the same interval). Also, that the difference between the two lengths in $[2,4[$ is greater than or equal to 1. (So that we can't apply 1.) 

A. If we can find $a,b \in [4,10]$ so that $|a - b| < 3$, we are done because there is a $c \in [2,4[$ so that $c \geq 3$ (Using 3. and the assumptions) 
B. If we can't find $a,b \in [4,10]$ so that $|a - b| < 3$, that means the lengths are $4,7,10$. But if we look at them, they are 3 sides of a triangle.

Finally, as we wish to distribute 7 lengths in 3 intervals, the Pigeonhole Principle can be used to guarantee that at least 3 line segments' lengths belong to a same interval, and therefore to satisfy the condition.

O2

For the difference to be a multiple of 7, the integers must have equal modulo 7 residues. To avoid having 15 with the same residue, 14 numbers with different modulo 7 residues can be picked ($14 * 7 = 98$). Thus, two numbers are left over and have to share a modulo 7 residue with the other numbers under the pigeonhole principle.

O3

Label the numbers in the set $x_1,\dots,x_{100}$, consider the 100 subsets $\{x_1\}, \{x_1,x_2\},\dots,\{x_1,\dots,x_{100}\}$ and for each of these subsets, compute its sum. If none of these sums are divisible by $100$, then there are $100$ sums and $99$ residue classes mod $100$ (excluding $0$). Therefore two of these sums are the same mod $100$, say $x_1+\cdots+x_i\equiv x_1+\cdots+x_j\pmod{100}$ (with $i<j$). Then $x_{i+1}+\cdots+x_j\equiv 0\pmod{100}$, and the subset $\{x_{i+1},\dots,x_j\}$ suffices.

O4

We can split up the circle into nine parts as shown below, where the smaller circle in the middle has a diameter of $2$.

[asy] draw(circle((0, 0), 1)); draw(circle((0, 0), 0.4)); draw(0.4*dir(0)--dir(0)); draw(0.4*dir(45)--dir(45)); draw(0.4*dir(90)--dir(90)); draw(0.4*dir(135)--dir(135)); draw(0.4*dir(180)--dir(180)); draw(0.4*dir(225)--dir(225)); draw(0.4*dir(270)--dir(270)); draw(0.4*dir(315)--dir(315)); [/asy]

By the pigeonhole principle, at least one of these parts must contain $2$ or more points. Any two points within the smallest circle must have a distance of less than $2$. For each of the $8$ outer regions, the maximum distance between $2$ points within the same region will be when the two points are on opposing corners, or when they are placed on the two outer corners.

First, we determine which of these lengths is longer. The segment shown in blue below has length $\frac{5\sqrt{2}}{4}$. Using $\sqrt{2}\approx 1.414$ to approximate this value, we get $\frac{7.07}{4} = 1.7675$. This value is slightly above $1.75$, which means it is closer to $A$ than $B$. Therefore, $BC$ is longer than $AC$ so we only need to verify that the length of $BC$ is less than $2$.

[asy] draw(circle((0, 0), 1)); draw(circle((0, 0), 0.4)); draw(0.4*dir(0)--dir(0)); draw(0.4*dir(45)--dir(45)); draw(0.4*dir(90)--dir(90)); draw(0.4*dir(135)--dir(135)); draw(0.4*dir(180)--dir(180)); draw(0.4*dir(225)--dir(225)); draw(0.4*dir(270)--dir(270)); draw(0.4*dir(315)--dir(315)); draw(dir(90)--dir(45), dashed); draw(dir(45)--(1/sqrt(2), 0), blue); draw(0.4*dir(90)--dir(45), red); dot("$A$", dir(90), N); dot("$B$", 0.4*dir(90), NW); dot("$C$", dir(45), NE); [/asy]

This distance is equal to the hypotenuse of a right triangle with legs of length $\frac{\sqrt{2}}{2}$ and $\frac{5-\sqrt{2}}{2}$, as shown below.

[asy] draw(circle((0, 0), 1)); draw(circle((0, 0), 0.4)); draw(0.4*dir(45)--dir(45)); draw(0.4*dir(90)--dir(90)); draw(0.4*dir(135)--dir(135)); draw(0.4*dir(180)--dir(180)); draw(0.4*dir(225)--dir(225)); draw(0.4*dir(270)--dir(270)); draw(0.4*dir(315)--dir(315)); draw(0.4*dir(45)--(0.4/sqrt(2), 0), dotted); draw((0.4/sqrt(2), 0)--dir(0), dotted); draw(0.4*dir(45)--dir(0), red); [/asy]

After using the pythagorean theorem, we find the red line above has length $\frac{\sqrt{29-10\sqrt2}}{2}$. Approximating this value using $\sqrt{2}\approx 1.414$, we get $\frac{\sqrt{29-14.14}}{2}=\frac{\sqrt{15.86}}{2}<\frac{4}{2}=2$.

Therefore, no two points within the same region can have a distance of $2$ or more. As stated earlier, at least one of these regions must have $2$ or more points, so there must be a pair of points with a distance of less than $2$.

O5

The pigeonhole principle is used in these solutions (PDF).

O6

In the worst case, consider that senator $S$ hates a set of 3 senators, while he himself is hated by a completely different set of 3 other senators. Thus, given one senator, there may be a maximum of 6 other senators whom he cannot work with. If we have a minimum of 7 committees, there should be at least one committee suitable for the senator $S$ after the assignment of the 6 conflicting senators.

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