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 (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 .