Problem

Source: 2018 USAMO 6, by Richard Stong

Tags: USAMO, 2018 USAMO 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$. Proposed by Richard Stong