BdMO Online Forum

1. Observe that,
   $f(x)-x\not\equiv0\pmod{3}$
   $\Longleftrightarrow f(x)\not\equiv x\pmod{3}$
2. Claim : $f$ is bijective.
   • $f$ is injective (one-one) :
     $f(a)=f(b)$
     $\Longrightarrow f(f(a))=f(f(b))$
     $\Longrightarrow a=b$
   • $f$ is surjective (onto) :
     Let $y\in S$. Let $x=f(y)$. Then $f(x)=y$.
   Since $f$ is bijective and surjective. So, $f$ is injective.

Anindya Biswas wrote: ↑

Sat Mar 27, 2021 2:57 pm

1. Observe that,
   $f(x)-x\not\equiv0\pmod{3}$
   $\Longleftrightarrow f(x)\not\equiv x\pmod{3}$
2. Claim : $f$ is bijective.
   • $f$ is injective (one-one) :
     $f(a)=f(b)$
     $\Longrightarrow f(f(a))=f(f(b))$
     $\Longrightarrow a=b$
   • $f$ is surjective (onto) :
     Let $y\in S$. Let $x=f(y)$. Then $f(x)=y$.
   Since $f$ is bijective and surjective. So, $f$ is injective.

Let'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\}\]
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=6$ 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=6$ ways, and for each selection, we can color them with $E, F$ in $2!=2$ ways.
So, total number of ways to use the colors $E,F$ is $6\times6\times2=72$.
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!=24$ different ways.

So, the total number of colorings, $\boxed{^4C_2\times^4C_2\times2!\times4!=1728}$.

Asif Hossain wrote: ↑

Sat Mar 27, 2021 3:03 pm

Anindya Biswas wrote: ↑

Sat Mar 27, 2021 2:57 pm

1. Observe that,
   $f(x)-x\not\equiv0\pmod{3}$
   $\Longleftrightarrow f(x)\not\equiv x\pmod{3}$
2. Claim : $f$ is bijective.
   • $f$ is injective (one-one) :
     $f(a)=f(b)$
     $\Longrightarrow f(f(a))=f(f(b))$
     $\Longrightarrow a=b$
   • $f$ is surjective (onto) :
     Let $y\in S$. Let $x=f(y)$. Then $f(x)=y$.
   Since $f$ is bijective and surjective. So, $f$ is injective.

Let'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\}\]
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=6$ 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=6$ ways, and for each selection, we can color them with $E, F$ in $2!=2$ ways.
So, total number of ways to use the colors $E,F$ is $6\times6\times2=72$.
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!=24$ different ways.

So, the total number of colorings, $\boxed{^4C_2\times^4C_2\times2!\times4!=1728}$.

Don't tell me that you did it on contest ..

Mehrab4226 wrote: ↑

Sat Mar 27, 2021 4:43 pm

I didn't think about $f$ could be bijective.
So it gave me a weird solution, a huge one in fact.

Dustan wrote: ↑

Sat Mar 27, 2021 5:08 pm

Mehrab4226 wrote: ↑

Sat Mar 27, 2021 4:43 pm

I didn't think about $f$ could be bijective.
So it gave me a weird solution, a huge one in fact.

what is your ans then?

Mehrab4226 wrote: ↑

Sat Mar 27, 2021 4:43 pm

I didn't think about $f$ could be bijective.
So it gave me a weird solution, a huge one in fact.

Asif Hossain wrote: ↑

Sat Mar 27, 2021 9:24 pm

Mehrab4226 wrote: ↑

Sat Mar 27, 2021 4:43 pm

I didn't think about $f$ could be bijective.
So it gave me a weird solution, a huge one in fact.

you are much better than me i $f(f(x))=x$ reminded me of involution and i knew that the function is bijective but i thought the question wanted $f(x)$ in $x$ terms so i gave the ans $0$