Difference between revisions of "2018 USAMO Problems/Problem 6"
(→Solution) |
|||
Line 13: | Line 13: | ||
− | Case 1: <math>n</math> is odd. If <math>n</math> is odd then there must be exactly one <math>k</math> such that <math>x_k = k</math>. This yields <math>b_n=n\cdot b_{n-1}</math>* which has the same parity as <math>b_{n-1}</math>, so we need only consider the parity of <math>b_n</math> for odd <math>n</math>. (*Note: This is wrong, as <math>b_n</math> is only the number of valid involutions for <math>1,2,...,n</math>, not <math>1,2,...,n+1</math> with one number removed.) | + | Case 1: <math>n</math> is odd. If <math>n</math> is odd then there must be exactly one <math>k</math> such that <math>x_k = k</math>. This yields <math>b_n=n\cdot b_{n-1}</math>* which has the same parity as <math>b_{n-1}</math>, so we need only consider the parity of <math>b_n</math> for odd <math>n</math>. (*<b>Note: This is wrong, as <math>b_n</math> is only the number of valid involutions for <math>1,2,...,n</math>, not <math>1,2,...,n+1</math> with one number removed.</b>) |
− | Case 2: <math>n</math> is even. If <math>n</math> is even then can be no <math>k</math> so that <math>x_k=k</math>, or else there must be at least two distinct numbers <math>k</math> and <math>j</math> so that <math>x_k=k</math> and <math>x_j=j</math> which violates the given conditions. Denote a pair of numbers that are swapped to arrive at the final permutation as the pair <math>(a,b)</math>. Then if a permutation yields an invalid arrangement there must be two pairs <math>(a,b)</math> and <math>(c,d)</math> such that <math>\frac{a^2}{b^2} = \frac{c^2}{d^2}</math>. But notice that the two pairs <math>(a,c)</math> and <math>(b,d)</math> will also result in an invalid arrangement. | + | Case 2: <math>n</math> is even. If <math>n</math> is even then can be no <math>k</math> so that <math>x_k=k</math>, or else there must be at least two distinct numbers <math>k</math> and <math>j</math> so that <math>x_k=k</math> and <math>x_j=j</math> which violates the given conditions. Denote a pair of numbers that are swapped to arrive at the final permutation as the pair <math>(a,b)</math>. Then if a permutation yields an invalid arrangement there must be two pairs <math>(a,b)</math> and <math>(c,d)</math> such that <math>\frac{a^2}{b^2} = \frac{c^2}{d^2}</math>. But notice that the two pairs <math>(a,c)</math> and <math>(b,d)</math> will also result in an invalid arrangement. So, there must be an even number of invalid arrangements (<b>Note: This proof doesn't work, as no specific pairing of invalid arrangements is constructed. Indeed, when three pairs all with the same fraction are present, this doesn't work.</b>), meaning the parity we desire is just the number of ways to separate <math>n</math> objects into <math>\frac n2</math> pairs! However, this is quite simply just <math>(n-1)(n-3)(n-5)\cdots(3)(1)</math>, which is clearly the product of odd numbers. So we conclude that there are an odd number of valid permutations <math>(x_1,x_2,x_3,\dots,x_n)</math>. <math>\blacksquare</math> |
Latest revision as of 04:36, 5 March 2023
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 (Note: This proof doesn't work, as no specific pairing of invalid arrangements is constructed. Indeed, when three pairs all with the same fraction are present, this doesn't work.), 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
.