BdMO Online Forum

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$ 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}$.

Asif Hossain wrote: ↑

Sat Mar 27, 2021 10:32 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$ 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}$.

(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)
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$

Anindya Biswas wrote: ↑

Sat Mar 27, 2021 3:07 pm

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 ..

I did it on the contest, but sadly, I forgot to multiply the $2!$.
This looks long cause I have to explain everything. In the contest time, you are just talking to yourself.

Pro_GRMR wrote: ↑

Mon Mar 29, 2021 1:21 am

Secondary Regional P8 Had:

Let $S=\left\{1,2,3,\dots,12\right\}$. How many functions $f:S\to S$ are there such that $f\left(f(x)\right)=x$ and $f(x)-x$ is divisible by $3$.

That would create a total of $10$ ways to make pairs within a set. Thus a total of $10*10*10=10^3$ such functions. Right? or am I doing something wrong here? I tried my best to understand your solution and I think... I get it.

meeyadya_lm wrote: ↑

Sun Mar 28, 2021 12:40 pm

Anindya Biswas wrote: ↑

Sat Mar 27, 2021 3:07 pm

Asif Hossain wrote: ↑

Sat Mar 27, 2021 3:03 pm

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

I did it on the contest, but sadly, I forgot to multiply the $2!$.
This looks long cause I have to explain everything. In the contest time, you are just talking to yourself.

Whoa,man! You did it on the exam (ignore whatever mistake you did) ??!!!! which category, brother ? You got all of the rest correct ?

Anindya Biswas wrote: ↑

Tue Mar 30, 2021 12:57 pm

meeyadya_lm wrote: ↑

Sun Mar 28, 2021 12:40 pm

Anindya Biswas wrote: ↑

Sat Mar 27, 2021 3:07 pm

I did it on the contest, but sadly, I forgot to multiply the $2!$.
This looks long cause I have to explain everything. In the contest time, you are just talking to yourself.

Whoa,man! You did it on the exam (ignore whatever mistake you did) ??!!!! which category, brother ? You got all of the rest correct ?

Thanks. But sadly I made another silly mistake in another question and I am just waiting for the result to publish.