Difference between revisions of "2010 USAJMO Problems/Problem 1"
m |
5849206328x (talk | contribs) |
||
Line 1: | Line 1: | ||
− | ==Problem== | + | == Problem == |
− | A permutation of the set of positive integers <math>[n] = {1,2,\ldots,n}</math> | + | A permutation of the set of positive integers <math>[n] = \{1, 2, \ldots, n\}</math> is a sequence <math>(a_1, a_2, \ldots, a_n)</math> such that each element of <math>[n]</math> appears precisely one time as a term of the sequence. For example, <math>(3, 5, 1, 2, 4)</math> is a permutation of <math>[5]</math>. Let <math>P(n)</math> be the number of permutations of <math>[n]</math> for which <math>ka_k</math> is a perfect square for all <math>1\leq k\leq n</math>. Find with proof the smallest <math>n</math> such that <math>P(n)</math> is a multiple of <math>2010</math>. |
− | is a sequence <math>(a_1,a_2,\ldots,a_n)</math> such that each element of <math>[n]</math> | ||
− | appears precisely one time as a term of the sequence. For example, | ||
− | <math>(3, 5, 1, 2, 4)</math> is a permutation of <math>[5]</math>. Let <math>P(n)</math> be the number of | ||
− | permutations of <math>[n]</math> for which <math>ka_k</math> is a perfect square for all | ||
− | <math>1 \ | ||
− | is a multiple of <math>2010</math>. | ||
− | == | + | == Solutions == |
− | We claim that the smallest | + | We claim that the smallest <math>n</math> is <math>67^2 = \boxed{4489}</math>. |
− | |||
− | |||
− | |||
− | is | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | We | + | === Solution 1 === |
− | + | Let <math>S = \{1, 4, 9, \ldots\}</math> be the set of positive perfect squares. We claim that the relation <math>R = \{(j, k)\in [n]\times[n]\mid jk\in S\}</math> is an equivalence relation on <math>[n]</math>. | |
− | + | * It is reflexive because <math>k^2\in S</math> for all <math>k\in [n]</math>. | |
− | + | * It is symmetric because <math>jk\in S\implies kj = jk\in S</math>. | |
− | <math> | + | * It is transitive because if <math>jk\in S</math> and <math>kl\in S</math>, then <math>jk\cdot kl = jlk^2\in S\implies jl\in S</math>, since <math>S</math> is closed under multiplication and a non-square times a square is always a non-square. |
− | + | We are restricted to permutations for which <math>ka_k \in S</math>, in other words to permutations that send each element of <math>[n]</math> into its equivalence class. Suppose there are <math>N</math> equivalence classes: <math>C_1, \ldots, C_N</math>. Let <math>n_i</math> be the number of elements of <math>C_i</math>, then <math>P(n) = \prod_{i=1}^{N} n_i!</math>. | |
− | |||
− | |||
− | |||
− | |||
− | \ | ||
− | + | Now <math>2010 = 2\cdot 3\cdot 5\cdot 67</math>. In order that <math>2010\mid P(n)</math>, we must have <math>67\mid n_m!</math> for the class <math>C_m</math> with the most elements. This means <math>n_m\geq 67</math>, since no smaller factorial will have <math>67</math> as a factor. This condition is sufficient, since <math>n_m!</math> will be divisible by <math>30</math> for <math>n_m\geq 5</math>, and even more so <math>n_m\geq 67</math>. | |
− | |||
− | |||
− | <math> | ||
− | since <math> | ||
− | |||
− | |||
− | + | The smallest element <math>g_m</math> of the equivalence class <math>C_m</math> is square-free, since if it were divisible by the square of a prime, the quotient would be a smaller element of <math>C_m</math>. Also, each prime <math>p</math> that divides <math>g_m</math> divides all the other elements <math>k</math> of <math>C_m</math>, since <math>p^2\mid kg_m</math> and thus <math>p\mid k</math>. Therefore <math>g_m\mid k</math> for all <math>k\in C_m</math>. The primes that are not in <math>g_m</math> occur an even number of times in each <math>k\in C_m</math>. | |
− | |||
− | |||
− | |||
− | == | + | Thus the equivalence class <math>C_m = \{g_mk^2\leq n\}</math>. With <math>g_m = 1</math>, we get the largest possible <math>n_m</math>. This is just the set of squares in <math>[n]</math>, of which we need at least <math>67</math>, so <math>n\geq 67^2</math>. This condition is necessary and sufficient. |
+ | === Solution 2 === | ||
This proof can also be rephrased as follows, in a longer way, but with fewer highly technical words such as "equivalence relation": | 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 <math>n</math> in the form <math>p\cdot m^2</math>, where <math>m^2</math> is the largest perfect square dividing <math>n</math>, so <math>p</math> is not divisible by the square of any prime. Obviously, one working permutation of <math>[n]</math> is simply <math>(1,2,\ldots,n)</math>; this is acceptable, as <math>ka_k</math> is always <math>k^2</math> in this sequence. | + | It is possible to write all positive integers <math>n</math> in the form <math>p\cdot m^2</math>, where <math>m^2</math> is the largest perfect square dividing <math>n</math>, so <math>p</math> is not divisible by the square of any prime. Obviously, one working permutation of <math>[n]</math> is simply <math>(1, 2, \ldots, n)</math>; this is acceptable, as <math>ka_k</math> is always <math>k^2</math> in this sequence. |
− | Lemma 1 | + | '''Lemma 1.''' We can permute any numbers that, when each divided by the largest perfect square that divides it, yield equal quantities <math>p</math>. |
− | Let <math>p_k</math> and <math>m_k</math> be the values of <math>p</math> and <math>m</math>, respectively, for a given <math>k</math> as defined above, such that <math>p</math> is not divisible by the square of any prime. We can obviously permute two numbers which have the same <math>p</math>, since if <math>p_j = p_w</math> where <math>j</math> and <math>w</math> are 2 values of <math>k</math>, then <math>j\cdot w | + | ''Proof.'' Let <math>p_k</math> and <math>m_k</math> be the values of <math>p</math> and <math>m</math>, respectively, for a given <math>k</math> as defined above, such that <math>p</math> is not divisible by the square of any prime. We can obviously permute two numbers which have the same <math>p</math>, since if <math>p_j = p_w</math> where <math>j</math> and <math>w</math> are 2 values of <math>k</math>, then <math>j\cdot w = p_j^2\cdot m_j^2\cdot m_w^2</math>, which is a perfect square. This proves that we can permute any numbers with the same value of <math>p</math>. |
− | + | '''End Lemma''' | |
− | Lemma 2 | + | '''Lemma 2.''' We will prove the converse of Lemma 1: Let one number have a <math>p</math> value of <math>\phi</math> and another, <math>\gamma</math>. <math>\phi\cdot f</math> and <math>\gamma\cdot g</math> are both perfect squares. |
− | <math>\phi\cdot f</math> and <math>\gamma\cdot g</math> are both perfect squares, so for <math>\phi\cdot \gamma</math> to be a perfect square, if <math>g</math> is greater than or equal to <math>f</math>, <math>g/f</math> must be a perfect square, too. Thus <math>g</math> is <math>f</math> times a square, but <math>g</math> cannot divide any squares besides <math>1</math>, so <math>g=1f</math>; <math>g=f</math>. Similarly, if <math>f\ | + | ''Proof.'' <math>\phi\cdot f</math> and <math>\gamma\cdot g</math> are both perfect squares, so for <math>\phi\cdot \gamma</math> to be a perfect square, if <math>g</math> is greater than or equal to <math>f</math>, <math>g/f</math> must be a perfect square, too. Thus <math>g</math> is <math>f</math> times a square, but <math>g</math> cannot divide any squares besides <math>1</math>, so <math>g = 1f</math>; <math>g = f</math>. Similarly, if <math>f\geq g</math>, then <math>f = g</math> for our rules to keep working. |
− | + | '''End Lemma''' | |
− | + | We can permute <math>l</math> numbers with the same <math>p</math> in <math>l!</math> ways. We must have at least 67 numbers with a certain <math>p</math> 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 <math>h</math>, in general, we need numbers all the way up to <math>h\cdot 67^2</math>, so obviously, <math>67^2</math> is the smallest such number such that we can get a <math>67!</math> term; here 67 <math>p</math> terms are 1. Thus we need the integers <math>1, 2, \ldots, 67^2</math>, so <math>67^2</math>, or <math>\boxed{4489}</math>, is the answer. | |
− | |||
− | |||
− | + | {{alternate solutions}} | |
== See Also == | == See Also == | ||
+ | * <url>viewtopic.php?t=347303 Discussion on AoPS/MathLinks</url> | ||
+ | |||
{{USAJMO newbox|year=2010|before=First Question|num-a=2}} | {{USAJMO newbox|year=2010|before=First Question|num-a=2}} | ||
[[Category:Olympiad Number Theory Problems]] | [[Category:Olympiad Number Theory Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 22:54, 15 August 2014
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 .
Solutions
We claim that the smallest is .
Solution 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.
Solution 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 .
Proof. 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.
Proof. 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
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.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
See Also
- <url>viewtopic.php?t=347303 Discussion on AoPS/MathLinks</url>
2010 USAJMO (Problems • Resources) | ||
Preceded by First Question |
Followed by Problem 2 | |
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.