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.
User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:
BdMO Regional 2021 Higher Secondary P8

Unread post by Anindya Biswas » Sat Mar 27, 2021 1:52 pm

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 not divisible by $3$.
Last edited by Anindya Biswas on Sun Mar 28, 2021 11:35 am, edited 1 time in total.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

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 2:33 pm

obs: for each $x \in S$ there are exactly $8$ numbers that you can pair ST $3$ doesn't divide $f(x)-x$ then think graphically how many graphs are possible??
(still didn't try :oops: )
Hmm..Hammer...Treat everything as nail

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 » 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}$.
Last edited by Anindya Biswas on Sat Mar 27, 2021 3:04 pm, edited 1 time in total.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

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

Re: Solution to BdMO Regional 2021 Higher Secondary P8

Unread post by Asif Hossain » 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 by the way "the function is bijective and surjective so the function is injective" :mrgreen:
Last edited by Asif Hossain on Sat Mar 27, 2021 9:26 pm, edited 1 time in total.
Hmm..Hammer...Treat everything as nail

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 » 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.
"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
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: BdMO Regional 2021 Higher Secondary P8

Unread post by Mehrab4226 » Sat Mar 27, 2021 4:43 pm

I didn't think about $f$ could be bijective. :cry: :cry: :cry:
So it gave me a weird solution, a huge one in fact.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

Dustan
Posts:71
Joined:Mon Aug 17, 2020 10:02 pm

Re: BdMO Regional 2021 Higher Secondary P8

Unread post by Dustan » 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. :cry: :cry: :cry:
So it gave me a weird solution, a huge one in fact.
what is your ans then?

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: BdMO Regional 2021 Higher Secondary P8

Unread post by Mehrab4226 » Sat Mar 27, 2021 6:46 pm

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. :cry: :cry: :cry:
So it gave me a weird solution, a huge one in fact.
what is your ans then?
$16777216$
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

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 9:24 pm

Mehrab4226 wrote:
Sat Mar 27, 2021 4:43 pm
I didn't think about $f$ could be bijective. :cry: :cry: :cry:
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$ :cry: :cry:
Hmm..Hammer...Treat everything as nail

Dustan
Posts:71
Joined:Mon Aug 17, 2020 10:02 pm

Re: BdMO Regional 2021 Higher Secondary P8

Unread post by Dustan » Sat Mar 27, 2021 9:27 pm

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. :cry: :cry: :cry:
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$ :cry: :cry:
Me too

Post Reply