2010 USAJMO Problems/Problem 1
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
Let be the set of positive perfect squares.
We claim that the relation $R = \{(j, k) \in [n]\times[n] \st jk \in S\}$ (Error compiling LaTeX. Unknown error_msg)
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.