Problem: Let $a_n$ be the number of permutations $(x_1, \dots, x_n)$ of $(1, \dots, n)$
such that the ratios $x_k / k$ are all distinct.
Prove that $a_n$ is odd for all $n \ge 1$.

\end{enumerate}

Solution: This is the official solution; the proof has two main insights.

The first idea:
\begin{lemma*}
  If a permutation $x$ works, so does the inverse permutation.
\end{lemma*}

Thus it suffices to consider permutations $x$
in which all cycles have length at most $2$.
Of course, there can be at most one fixed point (since that gives the ratio $1$),
and hence exactly one if $n$ is odd, none if $n$ is even.

We consider the graph $K_n$ such that the edge
$\{i,j\}$ is labeled with $i / j$ (for $i < j$).
The permutations we're considering are then equivalent to maximal
matchings of this $K_n$.
We call such a matching \emph{fantastic} if it has all distinct edge labels.

\bigskip

Now the second insight is that if edges $ab$ and $cd$
have the same label for $a<b$ and $c<d$, then so do edges $ac$ and $bd$.
Thus:
\begin{definition*}
  Given a matching $\mathcal M$ as above we say the \emph{neighbors}
  of $\mathcal M$ are those other matchings obtained as follows:
  for each label $\ell$, we take some disjoint pairs of edges (possibly none)
  with label $\ell$ and apply the above switching operation
  (in which we replace $ab$ and $cd$ with $ac$ and $bd$).
\end{definition*}
This neighborship relation is reflexive, and most importantly it is \emph{symmetric}
(because one can simply reverse the moves).
But it is not transitive.

The second observation is that:
\begin{claim*}
  The matching $\mathcal M$ has an odd number of neighbors
  (including itself) if and only if it is fantastic.
\end{claim*}
\begin{proof}
  Consider the label $\ell$, and assume it appears $n_\ell \ge 1$ times.

  If we pick $k$ disjoint pairs and swap them, the number of ways to do this is
  $\binom{n_\ell}{2k} (2k-1)!!$, and so the total
  number of ways to perform operations on the edges labeled $\ell$ is
  \[ \sum_k \binom{n_\ell}{2k} (2k-1)!!
    \equiv \sum_k \binom{n_\ell}{2k}
    = 2^{n_\ell-1} \pmod 2. \]
  This is even if and only if $n_\ell > 1$.

  Finally, note that the number of neighbors
  of $\mathcal M$ is the product across all $\ell$ of the above.
  So it is odd if and only if each factor is odd,
  if and only if $n_\ell = 1$ for every $\ell$.
\end{proof}

To finish, consider a huge simple graph $\Gamma$ on all the
maximal matchings, with edge relations given by neighbor relation
(we don't consider vertices to be connected to themselves).
Observe that:
\begin{itemize}
  \ii The fantastic matchings of the vertices of $\Gamma$ have odd degrees
  (one less than the neighbor count).
  \ii The other matchings correspond to isolated vertices
  (of degree zero, with no other neighbors) of $\Gamma$.
  \ii The graph $\Gamma$ has an even number of vertices of odd degree
  (this is true for any simple graph, see ``handshake lemma'').
  \ii The number of vertices of $\Gamma$ is odd,
  namely $\left( 2\left\lceil n/2 \right\rceil - 1 \right)!!$.
\end{itemize}
This concludes the proof.