Difference between revisions of "2010 USAJMO Problems/Problem 1"

Revision as of 21:58, 1 August 2018

This problem has been removed mercilessly.

Solution Number Sense

We have to somehow calculate the number of permutations for a given $n$ . How in the world do we do this? Because we want squares, why not call a number $k=m*s^2$ , where $s$ is the largest square that allows $m$ to be non-square? $m=1$ is the only square $m$ can be, which only happens if $k$ is a perfect square.

For example, $126 = 14 * 3^2$ , therefore in this case $k=126, m = 14, s = 3$ .

I will call a permutation of the numbers $P$ , while the original $1, 2, 3, 4, ...$ I will call $S$ .

Note that essentially we are looking at "pairing up" elements between $P$ and $S$ such that the product of $P_k$ and $S_k$ 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 $mod 2$ and if there are any odd numbers, those are the ones we have to match- in effect, they are the $m$ numbers mentioned at the beginning.

By listing the $m$ values, in my search for "dumb" or "obvious" ideas I am pretty confident that only values with identical $m$ s can be matched together. With such a solid idea let me prove it.

If we were to "pair up" numbers with different $m$ s, take for example $S_{18}$ with an $m$ of $2$ and $P_{18}=26$ with an $m$ of $26$ , note that their product gives a supposed $m$ of $13$ because the $2$ values cancel out. But then, what happens to the extra $13$ left? It doesn't make a square, contradiction. To finish up this easy proof, note that if a "pair" has different $m$ values, and the smaller one is $m_1$ , in order for the product to leave a square, the larger $m$ value has to have not just $m_1$ but another square inside it, which is absurd because we stipulated at the beginning that $m$ was square-free except for the trivial multiplication identity, 1.

Now, how many ways are there to do this? If there are $c_1$ numbers with $m=1$ , there are clearly $(c_1)!$ ways of sorting them. The same goes for $m=2, 3, etc.$ by this logic. Note that the $P(n)$ as stated by the problem requires a $67$ thrown in there because $2010=2*3*5*67$ , so there has to be a $S_n$ with 67 elements with the same $m$ . It is evident that the smallest $n$ will occur when $m=1$ , because if $m$ is bigger we would have to expand $n$ to get the same number of $m$ values. Finally, realize that the only numbers with $m=1$ are square numbers! So our smallest $n=67^2=4489$ , 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 are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

@@ Line 3: / Line 3: @@
 This problem has been removed mercilessly.
-This problem has been removed mercilessly.
+==Solution Number Sense==
+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 ==

2010 USAJMO (Problems • Resources)
Preceded by First Question	Followed by Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions

Page

Toolbox

Search

Difference between revisions of "2010 USAJMO Problems/Problem 1"

Revision as of 21:58, 1 August 2018

Solution Number Sense

See Also