(Please clarify)Well i find a contradiction with PCO's solu with your solu (Please somebody notify me if it is legal to post solu from aops to another forum)Anindya Biswas wrote: ↑Sat Mar 27, 2021 2:57 pmLet's partition $S$ into $3$ equivalent classes. \[S_1=\{1,4,7,10\}\]\[S_2=\{2,5,8,11\}\]\[S_3=\{3,6,9,12\}\]
- Observe that,
$f(x)-x\not\equiv0\pmod{3}$
$\Longleftrightarrow f(x)\not\equiv x\pmod{3}$- Claim : $f$ is bijective.
- $f$ is injective (one-one) :
$f(a)=f(b)$
$\Longrightarrow f(f(a))=f(f(b))$
$\Longrightarrow a=b$Since $f$ is bijective and surjective. So, $f$ is injective.
- $f$ is surjective (onto) :
Let $y\in S$. Let $x=f(y)$. Then $f(x)=y$.
Notice that $x$ and $y$ are in same class if and only if $x\equiv y\pmod{3}$
We will now color the elements of $S$ using $6$ colors from the set $\{A,B,C,D,E,F\}$ with the rule that $x$ and $y$ gets same color if they are images of each other under $f$ and gets different colors otherwise. We will consider two colorings same if one can be obtained just by permuting the colors of the other. This means each coloring of the elements of $S$ corresponds to a function $f$. So, the number of such colorings is the same as the number of such functions.
Observe that if $x$ and $y$ are in same equivalent class [$x\equiv y\pmod{3}$], then $x$ and $y$ must get different colors for the first observation.
Let's color the elements $1,4,7,10$ with $A,B,C,D$ respectively.
Now we have to select $2$ elements from $S_2$ which would be colored with $E$ and $F$ such that the smaller element gets the color $E$. This can be done in $^4C_2$ ways.
Now we have to select $2$ elements from $S_3$ which would get the colors $E,F$. We can select $2$ elements from $S_3$ in $^4C_2$ ways, and for each selection, we can color them with $E, F$ in $2!$ ways.
We have colored $8$ elements and we are just left with $4$ more elements. Also, $4$ colors are left, $A,B,C,D$ since each color appears twice. We can color the $4$ elements with $4$ colors in $4!$ different ways.
So, the total number of colorings, $\boxed{^4C_2\times^4C_2\times2!\times4!=1728}$.
PCO solved the otherwise and showed that the function that are divisible by 3 are $13^3$
and i found from my "immense" logic that the number of bijective function is $12!$ so the functions that are not divisble by 3 is $12!-13^3$