|
|
| Line 3: |
Line 3: |
| | This problem has been removed mercilessly. | | This problem has been removed mercilessly. |
| | | | |
| − | ==Solution Number Sense==
| + | This problem has been removed mercilessly. |
| − | We have to somehow calculate the number of permutations for a given <math>n</math>. How in the world do we do this? Because we want squares, why not call a number <math>k=m*s^2</math>, where <math>s</math> is the largest square that allows <math>m</math> to be non-square? <math>m=1</math> is the only square <math>m</math> can be, which only happens if <math>k</math> is a perfect square.
| |
| − | | |
| − | For example, <math>126 = 14 * 3^2</math>, therefore in this case <math>k=126, m = 14, s = 3</math>.
| |
| − | | |
| − | I will call a permutation of the numbers <math>P</math>, while the original <math>1, 2, 3, 4, ...</math> I will call <math>S</math>.
| |
| − | | |
| − | Note that essentially we are looking at "pairing up" elements between <math>P</math> and <math>S</math> such that the product of <math>P_k</math> and <math>S_k</math> is a perfect square. How do we do this? Using the representation above.
| |
| − | | |
| − | Each square has to have an even exponent of every prime represented in its prime factorization. Therefore, we can just take all exponents of the primes <math>mod 2</math> and if there are any odd numbers, those are the ones we have to match- in effect, they are the <math>m</math> numbers mentioned at the beginning.
| |
| − | | |
| − | By listing the <math>m</math> values, in my search for "dumb" or "obvious" ideas I am pretty confident that only values with identical <math>m</math>s can be matched together. With such a solid idea let me prove it.
| |
| − | | |
| − | If we were to "pair up" numbers with different <math>m</math>s, take for example <math>S_{18}</math> with an <math>m</math> of <math>2</math> and <math>P_{18}=26</math> with an <math>m</math> of <math>26</math>, note that their product gives a supposed <math>m</math> of <math>13</math> because the <math>2</math> values cancel out. But then, what happens to the extra <math>13</math> left? It doesn't make a square, contradiction. To finish up this easy proof, note that if a "pair" has different <math>m</math> values, and the smaller one is <math>m_1</math>, in order for the product to leave a square, the larger <math>m</math> value has to have not just <math>m_1</math> but another square inside it, which is absurd because we stipulated at the beginning that <math>m</math> was square-free except for the trivial multiplication identity, 1.
| |
| − | | |
| − | Now, how many ways are there to do this? If there are <math>c_1</math> numbers with <math>m=1</math>, there are clearly <math>(c_1)!</math> ways of sorting them. The same goes for <math>m=2, 3, etc.</math> by this logic. Note that the <math>P(n)</math> as stated by the problem requires a <math>67</math> thrown in there because <math>2010=2*3*5*67</math>, so there has to be a <math>S_n</math> with 67 elements with the same <math>m</math>. It is evident that the smallest <math>n</math> will occur when <math>m=1</math>, because if <math>m</math> is bigger we would have to expand <math>n</math> to get the same number of <math>m</math> values. Finally, realize that the only numbers with <math>m=1</math> are square numbers! So our smallest <math>n=67^2=4489</math>, and we are done.
| |
| − | | |
| − | I relied on looking for patterns a lot in this problem. When faced with combo/number theory, it is always good to draw a sketch. Never be scared to try a problem on the USAJMO. It takes about 45 minutes. Well, it's 2010 and a number 1. Cheers!
| |
| − | | |
| − | -expiLnCalc
| |
| − | | |
| − | {{alternate solutions}}
| |
| | | | |
| | == See Also == | | == See Also == |
