HMMT-Feb 2021 comb, Problem 4

Let $S=\{1,2, \ldots, 9\}$. Compute the number of functions $f: S \rightarrow S$ such that, for all $s \in S, f(f(f(s)))=$ $s$ and $f(s)-s$ is not divisible by 3 .

Solution: Solution: Since $f(f(f(s)))=s$ for all $s \in S$, each cycle in the cycle decomposition of $f$ must have length 1 or 3 . Also, since $f(s) \not \equiv s$ mod 3 for all $s \in S$, each cycle cannot contain two elements $a, b$ such that $a=b \bmod 3$. Hence each cycle has exactly three elements, one from each of residue classes mod 3 . In particular, 1, 4, 7 belong to distinct cycles. There are $6 \cdot 3$ ways to choose two other numbers in the cycle containing 1 . Then, there are $4 \cdot 2$ ways to choose two other numbers in the cycle containing 4 . Finally, there are $2 \cdot 1$ ways to choose two other numbers in the cycle containing 7 . Hence the desired number of functions $f$ is $6 \cdot 3 \cdot 4 \cdot 2 \cdot 2 \cdot 1=288$. $\fbox{288}$.

Answer: 288