USAMO 2018 Problem 6

Let \(a_n\) be the number of permutations \((x_1, x_2, \dots, x_n)\) of the numbers \((1,2,\dots, n)\) such that the \(n\) ratios \(\frac{x_k}{k}\) for \(1\le k\le n\) are all distinct. Prove that \(a_n\) is odd for all \(n\ge 1\).

=========================================================

Intially it seems extremely hard, sounding like a combination of number theory and combinatorics. But with hindsight, asking only for parity reduces its difficulty by a great amount.

Sadly, I only managed to fill in the details after seeing two very crucial hints. Perhaps I didn't try hard enough though, but I intentionally didn't want to spend too much time on competition problems. This is a great excuse LOL. My initial sketch of proof consisted of a conjecture in number theory, which I didn't finish to prove, followed by combinatorial counting which is complete.

Below, we say a permutation is good if it satisfies the condition in the statement; otherwise it's bad. \(n=1\) is trivially ignored.

=========================================================

Hint #1: consider permutation and its inverse.

Define involution as permutation that equals its inverse. By definition involutions are those that consist only of pairs and singletons.

We pair non-involution permutations with their inverse, and quickly see that since a permutation is good if and only if its inverse is good, the numbers of either good or bad non-involution permutation is even.

Now, define maximal involution as those with at most one fixed point. Clearly a good permutation must be a maximal involution because non-maximal involution has ratio \(1\) appears more than once. How many non-maximal involutions are there? To obtain a non-maximal involution, we select \(2k\le n-2\) elements and then pair them into \(k\) pairs. There are \((2k-1)(2k-3)\ldots1\) pairings, so the parity of the number of non-maximal involutions equals to that of the number of ways to select \(2k\le n-2\) elements, which is odd.

This implies the statement is equivalent to that there are even number of bad maximal involutions. Unfortunately, pairing techniques couldn't be applied directly here and that's why I got stuck again and needed the second hint :(

=========================================================

Hint #2: consider adjacency between bad maximal involutions

A bad maximal involution has \(\frac{a_i}{i}=\frac{a_j}{j}\) where all four numbers are distinct, so we can swap two of them to get another bad maximal involution. We define a bad maximal involution \(a\) is adjacent to another bad maximal involution \(b\) if from \(a\) we can perform \(k\ge 1\) swaps on \(4k\) elements to reach \(b\). If in the graph every node has odd degree, then the graph of bad maximal involutions must have even number of nodes. So what is the degree of a given node? Group ratios less than or equal to one into clusters such that ratios in the same cluster are all equal, i.e. there is at least a cluster with more than one ratios. In a cluster of size \(m\ge 2\), similarly we pick \(2k\le m\) ratios and make \(k\) pairs, which similarly gives \(f(m)\), an even number of ways. Suppose a bad maximal involution has \(i\) non-singleton clusters with sizes \(m_1,\ldots,m_i\), then its degree is \(\prod f(m_i)-1\), which is odd as desired.