Question 119
For each positive integer $n$, let $a_{n}$ be the number of permutations $\tau$ of $\{1,2, \ldots, n\}$ such that $\tau(\tau(\tau(x)))=x$ for $x=1,2, \ldots, n$. The first few values are
$$
a_{1}=1,\ a_{2}=1,\ a_{3}=3,\ a_{4}=9.
$$
Prove that $3^{334}$ divides $a_{2001}$.
(A permutation of $\{1,2, \ldots, n\}$ is a rearrangement of the numbers $\{1,2, \ldots, n\}$, or equivalently, a one-to-one and onto function from $\{1,2, \ldots, n\}$ to $\{1,2, \ldots, n\}$. For example, one permutation of $\{1,2,3\}$ is the rearrangement $\{2,1,3\}$, which is equivalent to the function $\sigma:\{1,2,3\} \rightarrow\{1,2,3\}$ defined by $\sigma(1)=2,\ \sigma(2)=1,\ \sigma(3)=3$.)
$$
a_{1}=1,\ a_{2}=1,\ a_{3}=3,\ a_{4}=9.
$$
Prove that $3^{334}$ divides $a_{2001}$.
(A permutation of $\{1,2, \ldots, n\}$ is a rearrangement of the numbers $\{1,2, \ldots, n\}$, or equivalently, a one-to-one and onto function from $\{1,2, \ldots, n\}$ to $\{1,2, \ldots, n\}$. For example, one permutation of $\{1,2,3\}$ is the rearrangement $\{2,1,3\}$, which is equivalent to the function $\sigma:\{1,2,3\} \rightarrow\{1,2,3\}$ defined by $\sigma(1)=2,\ \sigma(2)=1,\ \sigma(3)=3$.)