Difference between revisions of "2010 USAJMO Problems/Problem 1"
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 == | == See Also == |
Revision as of 22:58, 1 August 2018
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 . How in the world do we do this? Because we want squares, why not call a number
, where
is the largest square that allows
to be non-square?
is the only square
can be, which only happens if
is a perfect square.
For example, , therefore in this case
.
I will call a permutation of the numbers , while the original
I will call
.
Note that essentially we are looking at "pairing up" elements between and
such that the product of
and
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 and if there are any odd numbers, those are the ones we have to match- in effect, they are the
numbers mentioned at the beginning.
By listing the values, in my search for "dumb" or "obvious" ideas I am pretty confident that only values with identical
s can be matched together. With such a solid idea let me prove it.
If we were to "pair up" numbers with different s, take for example
with an
of
and
with an
of
, note that their product gives a supposed
of
because the
values cancel out. But then, what happens to the extra
left? It doesn't make a square, contradiction. To finish up this easy proof, note that if a "pair" has different
values, and the smaller one is
, in order for the product to leave a square, the larger
value has to have not just
but another square inside it, which is absurd because we stipulated at the beginning that
was square-free except for the trivial multiplication identity, 1.
Now, how many ways are there to do this? If there are numbers with
, there are clearly
ways of sorting them. The same goes for
by this logic. Note that the
as stated by the problem requires a
thrown in there because
, so there has to be a
with 67 elements with the same
. It is evident that the smallest
will occur when
, because if
is bigger we would have to expand
to get the same number of
values. Finally, realize that the only numbers with
are square numbers! So our smallest
, 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.
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.