USAMO 2018 — Days 1 and 2 Question 6

Let $a_n$ count permutations $(x_1,\ldots,x_n)$ of $(1,\ldots,n)$ for which all ratios $x_k/k$ are distinct. Prove that $a_n$ is odd for every $n\ge1$.

Proposed by Richard Stong. Source: Evan Chen’s third-party compilation, not an official publication. One editorial point; manual grading only.