My friend shared the following problem with me. The problem is from Bangladesh Mathematical Olympiad 2021 (Divisional round).
Let $ A=\{1,2,3,\dots,12\}$. How many functions $g:A\to A$ are there such that $g(g(x))=x$ and $g(x)-x$ is not divisible by $3$?
Here is my progress in solving the problem:
We partition the sets modulo $3$. Let $A_0=\{3,6,9,12\}$, $A_1=\{1,4,7,10\}$, $A_2=\{2,5,8,11\}$. Because $g(g(x))=x$ the function will be fixed if we fix the values of the function for $6$ numbers. Let $g(1)=k$, then $k\notin A_1$ and $g(k)=1$. This means $k$ can take $8$ values. Similar argument leads that $g(4)$, $g(7)$, $g(10)$ can take $7$, $6$ and $5$ values respectively.
I can't proceed from here because I need to find the number of values the function can take for $2$ more numbers for the function to be fixed. But I can say that the final answer will be greater than $8\cdot7\cdot6\cdot5=1680$ from my approach.
From the comments, I realized that my approach is wrong. Then how do I solve the problem?
Best Answer
Since, $g(g(x))=x$ for all $x$, it is not hard to see that $g(x)$ must be a bijection with only $2$-cycles and $1$-cycles. Since $g(x)-x\not\equiv 0\mod 3$, we have that $g(x)\neq x$, hence, it must only have $2$-cycles.
So, now we can figure out how many ways there are to split the set $\{1,2,\ldots ,12\}$ into $6$ unordered pairs $\{a,b\}$ (we would then have $f(a)=b$ and $f(b)=a$) such that each ordered pair satisfies $a\not\equiv b\mod 3$.
Now as you tried, split the set into $3$ sets $A_0,A_1,A_2$ depending on the elements equivalence in$\mod 3$. Note that if the number of unordered pairs containing an element from $A_0$ and $A_1$ is not $2$, then we will have to have at least one unordered pair that contains $2$ elements from $A_2$, which is not allowed.
Hence, by symmetry, we must have that there are exactly $2$ unordered pairs containing elements from sets $A_i$ and $A_j$ for $i,j\in \{0,1,2\}$
From there, it is straight forward counting. There are $\binom{4}{2}^2$ ways to pick the elements from sets $A_0$ and $A_1$ that will be together in an unordered pair. If those elements are $a,b\in A_0$ and $c,d\in A_1$, then there are $2$ ways to assign the pairs ($\{a,c\},\{b,d\}$ and $\{a,d\},\{b,c\}$.
For the remaining two elements in $A_0$, there are $4\cdot 3$ ways to assign elements of $A_2$ that will be paired with these elements of $A_0$.
Now for the pairings of the $2$ remaining elements of $A_1$ with those of $A_2$. There are exactly $2$ ways to assign these pairings.
So our total is $2\cdot \binom{4}{2}^2\cdot 4\cdot 3\cdot 2=(12)^3=\boxed{1728}$