Difference between revisions of "2010 USAJMO Problems/Problem 5"
Alexlikemath (talk | contribs) |
Alexlikemath (talk | contribs) |
||
Line 58: | Line 58: | ||
(constructed by continuously rotating the first 1006 numbers) | (constructed by continuously rotating the first 1006 numbers) | ||
− | satisfy the property that any other permutation will intersect with | + | satisfy the property that any other permutation will intersect with at least one of these permutations. |
'''Proof''': | '''Proof''': |
Revision as of 12:24, 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 claim that the permutations:
[1, 2, 3 ... 1005, 1006, 1007 ... 2009, 2010]
[2, 3, 4 ... 1006, 1, 1007 ... 2009, 2010]
...
...
...
[1006, 1, 2 ... 1005, 1007, ... 2009, 2010]
(constructed by continuously rotating the first 1006 numbers)
satisfy the property that any other permutation will intersect with at least one of these permutations.
Proof: Assume that there exists a permutation that won't intersect with these, say . If , , we get an intersection. So, for all , . There are 1004 numbers such that , but we need to have 1006 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 that any other permutation does intersect at least 1 of the permutations. 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.