BdMO Regional 2021 Higher Secondary P8

Forum rules
Please don't post problems (by starting a topic) in the "X: Solved" forums. Those forums are only for showcasing the problems for the convenience of the users. You can always post the problems in the main Divisional Math Olympiad forum. Later we shall move that topic with proper formatting, and post in the resource section.
Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm
Re: BdMO Regional 2021 Higher Secondary P8

Unread post by Asif Hossain » 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$
Hmm..Hammer...Treat everything as nail

Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm

Re: BdMO Regional 2021 Higher Secondary P8

Unread post by Asif Hossain » Sat Mar 27, 2021 10:43 pm

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$
o sorry now i understand it is not necessary to every bijective function to be $f(f(x))=x$ :lol:
Hmm..Hammer...Treat everything as nail

meeyadya_lm
Posts:1
Joined:Sun Mar 28, 2021 12:15 pm

Re: Solution to BdMO Regional 2021 Higher Secondary P8

Unread post by meeyadya_lm » 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
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 .. :o :o
I did it on the contest, but sadly, I forgot to multiply the $2!$. :( :oops:
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 ?

User avatar
Pro_GRMR
Posts:46
Joined:Wed Feb 03, 2021 1:58 pm

Re: BdMO Regional 2021 Higher Secondary P8

Unread post by Pro_GRMR » 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.

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: BdMO Regional 2021 Higher Secondary P8

Unread post by Anindya Biswas » Mon Mar 29, 2021 7:37 pm

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.
Thanks for providing the solution. Actually they gave different questions to different people. Some got the not divisible version and some got the divisible version.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: Solution to BdMO Regional 2021 Higher Secondary P8

Unread post by Anindya Biswas » 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
Asif Hossain wrote:
Sat Mar 27, 2021 3:03 pm

Don't tell me that you did it on contest .. :o :o
I did it on the contest, but sadly, I forgot to multiply the $2!$. :( :oops:
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.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
Pro_GRMR
Posts:46
Joined:Wed Feb 03, 2021 1:58 pm

Re: Solution to BdMO Regional 2021 Higher Secondary P8

Unread post by Pro_GRMR » Tue Mar 30, 2021 1:04 pm

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!$. :( :oops:
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.
No worries pco makes mistake too. 8-)
"When you change the way you look at things, the things you look at change." - Max Planck

Post Reply