2010 USAJMO Problems/Problem 1
Contents
[hide]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
We claim that the smallest n is .
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":
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 .
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.
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
Lemma 3: Getting to the answer
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.
END LEMMA
Q.E.D.
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.