Difference between revisions of "Pigeonhole Principle/Solutions"
Diabologuy (talk | contribs) (→M1) |
(Add solution and remove dead link) |
||
Line 35: | Line 35: | ||
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=== | ||
− | + | 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 is 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. | 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. |
Revision as of 11:58, 30 March 2013
These are the solutions to the problems related to the Pigeonhole Principle.
Contents
[hide]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 can be less than the sum of the other two sides. Assume that the first two segments are as short as possible (1 inch). For a triangle to not exist, the next term must be 2, then 3, 5, 8, and 13 (this is the Fibonacci sequence). The 7th term is 13, which is greater than 10 inches.
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.