Difference between revisions of "2010 USAJMO Problems/Problem 1"
Jiminhio 10 (talk | contribs) (→Proof 2) |
m (added a See Also section) |
||
Line 73: | Line 73: | ||
Q.E.D. | Q.E.D. | ||
+ | |||
+ | == See Also == | ||
+ | {{USAJMO newbox|year=2005|before=First Question|num-a=3}} | ||
+ | |||
+ | [[Category:Olympiad Number Theory Problems |
Revision as of 10:40, 15 April 2012
Contents
[hide]Problem
A permutation of the set of positive integers is a sequence such that each element of appears precisely one time as a term of the sequence. For example, is a permutation of . Let be the number of permutations of for which is a perfect square for all . Find with proof the smallest such that is a multiple of .
Solution
The smallest .
Proof 1
Let be the set of positive perfect squares. We claim that the relation is an equivalence relation on .
- It is reflexive because for all .
- It is symmetric because .
- It is transitive because if and , then , since is closed under multiplication and a non-square times a square is always a non-square.
We are restricted to permutations for which , in other words to permutations that send each element of into its equivalence class. Suppose there are equivalence classes: . Let be the number of elements of , then
Now . In order that , we must have for the class with the most elements. This means , since no smaller factorial will have as a factor. This condition is sufficient, since will be divisible by for , and even more so .
The smallest element of the equivalence class is square-free, since if it were divisible by the square of a prime, the quotient would be a smaller element of . Also, each prime that divides divides all the other elements of , since and thus . Therefore for all . The primes that are not in occur an even number of times in each .
Thus the equivalence class . With , we get the largest possible . This is just the set of squares in , of which we need at least , so . This condition is necessary and sufficient.
Proof 2
This proof can also be rephrased as follows, in a longer way, but with fewer highly technical words such as "equivalence relation":
It is possible to write all positive integers in the form , where is the largest perfect square dividing , so is not divisible by the square of any prime. Obviously, one working permutation of is simply ; this is acceptable, as is always in this sequence.
Lemma 1: We can permute any numbers that, when each divided by the largest perfect square that divides it, yield equal quantities .
Let and be the values of and , respectively, for a given as defined above, such that is not divisible by the square of any prime. We can obviously permute two numbers which have the same , since if where and are 2 values of , then =, which is a perfect square. This proves that we can permute any numbers with the same value of .
END LEMMA
Lemma 2: We will prove the converse of Lemma 1: Let one number have a value of and another, . and are both perfect squares.
and are both perfect squares, so for to be a perfect square, if is greater than or equal to , must be a perfect square, too. Thus is times a square, but cannot divide any squares besides , so ; . Similarly, if , then for our rules to keep working.
END LEMMA
Lemma 3: Getting to the answer
We can permute numbers with the same in ways. We must have at least 67 numbers with a certain so our product will be divisible by 67. Obviously, then it will also be divisible by 2, 3, and 5, and thus 2010, as well. Toms as , in general, we need numbers all the way up to , so obviously, is the smallest such number such that we can get a term; here 67 terms are 1. Thus we need the integers , so , or , is the answer.
END LEMMA
Q.E.D.
See Also
2005 USAJMO (Problems • Resources) | ||
Preceded by First Question |
Followed by Problem 3 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAJMO Problems and Solutions |
[[Category:Olympiad Number Theory Problems