Difference between revisions of "2010 USAJMO Problems/Problem 1"
(Created page with '==Problem== A permutation of the set of positive integers <math>[n] = {1,2,\ldots,n}</math> is a sequence <math>(a_1,a_2,\ldots,a_n)</math> such that each element of <math>[n]</m…') |
(→Proof) |
||
Line 12: | Line 12: | ||
===Proof=== | ===Proof=== | ||
Let <math>S = \{1, 4, 9, \ldots\}</math> be the set of positive perfect squares. | Let <math>S = \{1, 4, 9, \ldots\}</math> be the set of positive perfect squares. | ||
− | We claim that the relation <math>R = \{(j, k) \in [n]\times[n] \ | + | We claim that the relation <math>R = \{(j, k) \in [n]\times[n] \mathrel{|} jk \in S\}</math> |
is an equivalence relation on <math>[n]</math>. | is an equivalence relation on <math>[n]</math>. | ||
<ul> | <ul> |
Revision as of 23:34, 6 May 2010
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
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.