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
.
Solution
The smallest .
Proof 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.
Proof 2
This proof can also be rephrased as follows, in a longer way, but with fewer highly technical words such as "equivalence relation":
A permutation of the set of positive integers is a sequence
such that each element of [n] 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 n such that
is a multiple of 2010.
Solution:
Write all positive integers in the form , where n squared is the largest perfect square dividing n, so k is not a perfect square. Obviously, we can write the positive integers in the form 1, 2, ,3... y; this is acceptable, as n times a sub n is always n squared in this sequence.
Lemma 1: We can permute any numbers which, when divided by the largest perfect square that divides them, yield equal quantites, the quanity "k" in this example.
We can obviously permute two numbers which have the same , the term multiplied by
, as if k(w) squared times m is a perfect square and so is k(j) squared times q, then k_m and k_q are perfect squares as are k(j) squared times m and similarly, k(w) squared times q is a perfect square. This proves that we can permute any two, and thus any numbers with the same "k"
END LEMMA
Lemma 2: We will prove the connverse of Lemma 1: Let one number have a k value of feta and another, gamma. feta times f and gamma times g are both perfect squares.
f and gamma g are both perfect squares, so for feta g to be a perfect square, so if g is greater than or equal to f, g/f must be a perfect square, too. Thus g is f times a square, but g cannot divide any squares besides 1, so g=1f and g=f. Similarly, if f>=g, then f=g for our rules to keep working.
END LEMMA
Lemma 3: Getting to the answer
We can permute l numbers with the same k in l! ways. We must have at least 67 numbers with a certain "k" so our produc wil be divisible by 67. Obviously, then it will be divisible by 2, 3, and 5, and thus 2010, as well. Obviously, 67 squared is the smallest such number so that we can get a 67! term; here 67 k terms are "1." To get 67 k terms as f, in general, we need numbers all the way up to . Thus we need the integers
, so
, or 4489, is the answer.
END LEMMA
Q.E.D.