Difference between revisions of "2010 USAJMO Problems/Problem 5"
Alexlikemath (talk | contribs) |
Alexlikemath (talk | contribs) (→Solution 2) |
||
Line 42: | Line 42: | ||
==Solution 2== | ==Solution 2== | ||
− | I | + | I construct the following permutations by continuously rotating the first 1006 numbers): |
− | + | (1, 2, 3 ... 1005, 1006, 1007 ... 2009, 2010) | |
− | + | (2, 3, 4 ... 1006, 1, 1007 ... 2009, 2010) | |
... | ... | ||
Line 54: | Line 54: | ||
... | ... | ||
− | + | (1006, 1, 2 ... 1005, 1007, ... 2009, 2010) | |
− | |||
− | satisfy the property that any other permutation will intersect with at least one of | + | |
+ | I claim that these permutations satisfy the property that any other permutation will intersect with at least one of them. | ||
'''Proof''': | '''Proof''': | ||
− | Assume that there exists a permutation that won't intersect with these, say <math>(a_1 ... a_{2010})</math>. If <math>a_k \leq 1006</math>, <math>1 \ | + | Assume that there exists a permutation that won't intersect with these, say <math>(a_1, a_2, a_3 ... a_{2010})</math>. |
+ | |||
+ | '''Lemma''': | ||
+ | If <math>a_k \leq 1006</math>, <math>1 \leq k \leq 1006</math>, we get an intersection. | ||
+ | |||
+ | Note that for any 2 distinct permutations in our list, the numbers in kth index must be different, since each permutation is a rotation of an previous permutation. Also, the numbers can't exceed 1006, so, each number must occur exactly once in the kth index. | ||
+ | |||
+ | Using the lemma, we get that for all <math>1 \geq k \geq 1006</math>, <math>2010 \geq a_k > 1006</math>. | ||
− | Thus, such a set of 1006 permutations does exist satisfying | + | But, there are 1004 numbers such that <math>2010 \geq n > 1006</math>, but we need to have 1004 numbers to fill in 1006 spots, and thus, by pigeonhole principle(the numbers are the holes, the spots are the pigeons), there must be 2 spots that have the same number! However, in a permutation, all numbers must be distinct, so we have a contradiction. |
+ | |||
+ | Thus, such a set of 1006 permutations does exist satisfying the given conditions. Thus, the proof is complete. | ||
-Alexlikemath | -Alexlikemath | ||
+ | |||
== See Also == | == See Also == | ||
{{USAJMO newbox|year=2010|num-b=4|num-a=6}} | {{USAJMO newbox|year=2010|num-b=4|num-a=6}} |
Revision as of 13:01, 18 June 2020
Contents
Problem
Two permutations and of the numbers are said to intersect if for some value of in the range . Show that there exist permutations of the numbers such that any other such permutation is guaranteed to intersect at least one of these permutations.
Solution 1
Let be a positive integer. Let be the smallest positive integer with . Since , . Let be the set of positive integers from to . Let , be .
Let be the set of of permutations of .
Let be the set of cyclic permutations of , there are cyclic permutations in all, and acts transitively on , i.e. for every pair of elements , there is an element of that maps to .
Let be the permutations in that leave fixed, and restricted to yield one of the permutations in . There is a natural one-to-one correspondence between and .
We claim that the permutations intersect every permutation in .
Suppose, to the contrary, that there exists a permutation that does not intersect any permutation in . Since acts transitively on the permutation cannot send any element of to any other element of , therefore it must send all the elements of to , but since has elements and , this is impossible by the pigeonhole principle. Therefore such a permutation cannot exist, and the permutations in intersect every permutation in .
For we get , which is the required special case of the general result above.
Solution 2
I construct the following permutations by continuously rotating the first 1006 numbers):
(1, 2, 3 ... 1005, 1006, 1007 ... 2009, 2010)
(2, 3, 4 ... 1006, 1, 1007 ... 2009, 2010)
...
...
...
(1006, 1, 2 ... 1005, 1007, ... 2009, 2010)
I claim that these permutations satisfy the property that any other permutation will intersect with at least one of them.
Proof: Assume that there exists a permutation that won't intersect with these, say .
Lemma: If , , we get an intersection.
Note that for any 2 distinct permutations in our list, the numbers in kth index must be different, since each permutation is a rotation of an previous permutation. Also, the numbers can't exceed 1006, so, each number must occur exactly once in the kth index.
Using the lemma, we get that for all , .
But, there are 1004 numbers such that , but we need to have 1004 numbers to fill in 1006 spots, and thus, by pigeonhole principle(the numbers are the holes, the spots are the pigeons), there must be 2 spots that have the same number! However, in a permutation, all numbers must be distinct, so we have a contradiction.
Thus, such a set of 1006 permutations does exist satisfying the given conditions. Thus, the proof is complete.
-Alexlikemath
See Also
2010 USAJMO (Problems • Resources) | ||
Preceded by Problem 4 |
Followed by Problem 6 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAJMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.