정수 $1$, $2$, $\ldots$, $n$으로 이루어진 순열 $(x_1,x_2,\ldots,x_n)$ 중 $n$개의 비율 $\frac{x_k}{k}$ (단, $1\le k\le n$)의 값이 모두 서로 다른 것의 수를 $a_n$이라 하자. 이때 모든 양의 정수 $n$에 대하여 $a_n$은 홀수임을 보여라.