Difference between revisions of "Pigeonhole Principle/Solutions"
(Add solution and remove dead link) |
(→O1) |
||
Line 31: | Line 31: | ||
==Olympiad== | ==Olympiad== | ||
===O1=== | ===O1=== | ||
− | By the [[Triangle Inequality]] Theorem, a side of a triangle | + | 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 substraction of the other two sides. |
+ | |||
+ | Consider the following statements: | ||
+ | |||
+ | 1. If we have at least 3 line segments to check and we take a line segment of length <math>a</math>, and a line segment of length <math>b</math> (so that <math>a \geq b</math> and <math>a - b < 1</math>); then when we take a line segment of length <math>c</math> (so that <math>a \geq 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 pick, 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 form <math>[k,2k[</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>c \geq b</math> and <math> c > a - b</math> | ||
+ | |||
+ | 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. There are <math>a,b,c \in [4,10]</math> so that <math>|a - b| < 1</math> or <math>|a - c| < 1</math> or <math>|b - c| < 1</math>. Then, due to 1. and the fact we have other lenghts in intervals which are less than <math>a,b,c</math> there will be three sides of a triangle. | ||
+ | |||
+ | |||
+ | B. The opposite is that the difference between any of <math>a,b,c \in [4,10]</math> is greater than or equal to <math>1</math>. | ||
+ | |||
+ | B1. 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.) | ||
+ | B1. 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, the Pigeon Principle can be used to guarantee that at least 3 line segments' lengths belong to a same interval, and therefore 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. |
Revision as of 01:59, 8 August 2013
These are the solutions to the problems related to the Pigeonhole Principle.
Contents
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 , modulo
. By the Pigeonhole Principle, there exist distinct
such that
, 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 to
friends; as there are
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
to
friends for the remaining friends not to also have no friends. By pigeonhole again, this leaves at least
other person with
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 , we have
Now, we wish to find a
between 1 and
such that
is within
of some integer.
Let
denote the fractional part of
.
Now, we sort the pigeons
into the holes $(0, 1/n}), (1/n, 2/n), \hdots, ((n - 1)/n, 1).$ (Error compiling LaTeX. Unknown error_msg)
If any pigeon falls into the first hole, we are done.
Therefore assume otherwise; then some two pigeons
for
.
Assume, without loss of generality, that
.
Then we have that
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 substraction of the other two sides.
Consider the following statements:
1. If we have at least 3 line segments to check and we take a line segment of length , and a line segment of length
(so that
and
); then when we take a line segment of length
(so that
), we will get that
and
are sides of a triangle. This is true because
. This means if we pick, for example,
and
then any number less than or equal to
will satisfy the condition of them being sides of a triangle.
2. If we have 3 line segments of lengths to check inside an interval form
we will find that they are sides of a triangle. This is true because
,
,
and
3. If we have 2 line segments of lengths so that
, then
are sides of a triangle if
and
Now let's consider the intervals ,
and
.
If we have 3 lines segment of lengths , then they are sides of a triangle because of 2.
If we have 3 lines segment of lengths , then they are sides of a triangle because of 2.
To analyze the case of having 3 lines segment of lengths , we can have two subcases. In both of them we will assume that 2 line segments' lengths are in
and 2 line segments' lengths are in
(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
is greater than or equal to 1. (So that we can't apply 1.)
A. There are so that
or
or
. Then, due to 1. and the fact we have other lenghts in intervals which are less than
there will be three sides of a triangle.
B. The opposite is that the difference between any of is greater than or equal to
.
B1. If we can findso that
, we are done because there is a
so that
(Using 3.) B1. If we can't find
so that
, that means the lengths are
. But if we look at them, they are 3 sides of a triangle.
Finally, the Pigeon Principle can be used to guarantee that at least 3 line segments' lengths belong to a same interval, and therefore 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 (). 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 , consider the 100 subsets
and for each of these subsets, compute its sum. If none of these sums is divisible by
, then there are
sums and
residue classes mod
(excluding
). Therefore two of these sums are the same mod
, say
(with
). Then
, and the subset
suffices.
O4
Inscribe a regular -gon, it will divide the circle into
equal arcs. The length of the side of this
-gon is
, 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.
O5
The pigeonhole principle is used in these solutions (PDF).
O6
This problem needs a solution. If you have a solution for it, please help us out by adding it.