2018 USAMO Problems/Problem 6
Problem 6
Let be the number of permutations
of the numbers
such that the
ratios
for
are all distinct. Prove that
is odd for all
Solution
Write out the mapping of each to
as follows:
Now, consider what happens when the two rows are swapped (and the top-bottom pairs are reordered so that the top reads (1,2,3,...,n)). This will result in a new permutation if and only if does not imply
for all
in
. I will denote this new permutation as
. Notice that
is a valid permutation if and only if
is valid, because each fraction
is the reciprocal of
. This means that we need only consider the parity of number of cases in which
, as there will be an even number of cases where
. Let the number of valid permutations where
be
.
Notice that the only permutations that have the property (which is an equivalent statement to the one given above) are those that are formed by taking pairs of elements and swapping their positions having the maximum number of pairs possible and having no two pairs both contain the same element. Some more necessary conditions will be outlined below after we split
into two cases.
Case 1: is odd. If
is odd then there must be exactly one
such that
. This yields
* which has the same parity as
, so we need only consider the parity of
for odd
. (*Note: This is wrong, as
is only the number of valid involutions for
, not
with one number removed.)
Case 2: is even. If
is even then can be no
so that
, or else there must be at least two distinct numbers
and
so that
and
which violates the given conditions. Denote a pair of numbers that are swapped to arrive at the final permutation as the pair
. Then if a permutation yields an invalid arrangement there must be two pairs
and
such that
. But notice that the two pairs
and
will also result in an invalid arrangement. So, there must be an even number of invalid arrangements, meaning the parity we desire is just the number of ways to separate
objects into
pairs! However, this is quite simply just
, which is clearly the product of odd numbers. So we conclude that there are an odd number of valid permutations
.