2010 USAJMO Problems/Problem 5
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.
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.
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 above satisfy the property that any other permutation will intersect with at least one of them.
Proof: Assume for the sake of contradiction that there exists a permutation that won't intersect with these, say .
Lemma: If there exists a k such that , we will get an intersection with the permutations.
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, in order to avoid intersections, we need , 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.
We have constructed a set of 1006 permutations. So, such a set of permutations exists satisfying that any permutation is guaranteed to intersect one of them, and the proof is complete.
|2010 USAJMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAJMO Problems and Solutions|