Difference between revisions of "2010 USAJMO Problems/Problem 5"
Alexlikemath (talk | contribs) |
|||
Line 8: | Line 8: | ||
permutations. | permutations. | ||
− | ==Solution== | + | ==Solution 1== |
Let <math>n</math> be a positive integer. Let <math>m</math> be the smallest positive integer with | Let <math>n</math> be a positive integer. Let <math>m</math> be the smallest positive integer with | ||
<math>m > n - m</math>. Since <math>n > n - n = 0</math>, <math>m \le n</math>. Let <math>N = \{1, \ldots, n\}</math> | <math>m > n - m</math>. Since <math>n > n - n = 0</math>, <math>m \le n</math>. Let <math>N = \{1, \ldots, n\}</math> | ||
Line 41: | Line 41: | ||
case of the general result above. | 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] | ||
+ | |||
+ | satisfy the property that any other permutation will intersect with this. | ||
+ | |||
+ | '''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 \geq k \geq 1006</math>, we get an intersection. So, for all <math>1 \geq k \geq 1006</math>, <math>2010 \leq a_k > 1006</math>. There are 1004 numbers such that <math>2010 \leq a_k > 1006</math>, 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. | ||
== 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 12:21, 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]
satisfy the property that any other permutation will intersect with this.
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.
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.