2010 USAJMO Problems/Problem 1
Contents
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.
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
Solution 4
Consider the set of numbers such that
is not divisible by any squares other than 1 and
By changing
we can encompass all numbers less than or equal to
. Now notice that for a working arrangement these numbers can be permutated in any way to create a new one; for instance, the numbers
have
and they can be arranged in
ways. Thus, since
we need a permutation to have at least 67 elements (since 67 is prime). To minimize
, we let
and we have
and we stop at
to get
. ~Leonard_my_dude~
Solution 5
It's well known that there exists and
such that
, no square divides
other than 1, and
is a perfect square.
Lemma:is a perfect square if and only if
![]()
We prove first: If ,
is a perfect square.
, which is a perfect square.
We will now prove: If is a perfect square,
.
We do proof by contrapositive: If ,
is not a perfect square.
is the p-adic valuation of k. (Basically how many factors of p you can take out of k)
Note that if , By the Fundamental Theorem of Arithmetic,
and
's prime factorization are different, and thus there exists a prime p, such that
. Also, since
and
is squarefree,
. Thus,
, making
not a square.
End Lemma
Thus, we can only match k with if they have the same f value. Thus, to find P(k), we can do it by f value, permuting the a_k with f value 1, then 2, ... Thus, our answer is:
For all ,
doesn't have a factor of 67. However, if
, the first term will be a multiple of 2010, and thus the answer is
-Alexlikemath
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.