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.
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.
- Anindya Biswas
- Posts:264
- Joined:Fri Oct 02, 2020 8:51 pm
- Location:Magura, Bangladesh
- Contact:
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
— John von Neumann
-
- Posts:194
- Joined:Sat Jan 02, 2021 9:28 pm
Re: BdMO Regional 2021 Higher Secondary P8
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 )
(still didn't try )
Hmm..Hammer...Treat everything as nail
- 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
- 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$
- $f$ is surjective (onto) :
Let $y\in S$. Let $x=f(y)$. Then $f(x)=y$.
- $f$ is injective (one-one) :
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
— John von Neumann
-
- Posts:194
- Joined:Sat Jan 02, 2021 9:28 pm
Re: Solution to BdMO Regional 2021 Higher Secondary P8
Don't tell me that you did it on contest .. by the way "the function is bijective and surjective so the function is injective"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=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}$.
Last edited by Asif Hossain on Sat Mar 27, 2021 9:26 pm, edited 1 time in total.
Hmm..Hammer...Treat everything as nail
- 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
I did it on the contest, but sadly, I forgot to multiply the $2!$.Asif Hossain wrote: ↑Sat Mar 27, 2021 3:03 pmDon't tell me that you did it on contest ..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=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}$.
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
— John von Neumann
- Mehrab4226
- Posts:230
- Joined:Sat Jan 11, 2020 1:38 pm
- Location:Dhaka, Bangladesh
Re: BdMO Regional 2021 Higher Secondary P8
I didn't think about $f$ could be bijective.
So it gave me a weird solution, a huge one in fact.
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é
-Henri Poincaré
Re: BdMO Regional 2021 Higher Secondary P8
what is your ans then?Mehrab4226 wrote: ↑Sat Mar 27, 2021 4:43 pmI didn't think about $f$ could be bijective.
So it gave me a weird solution, a huge one in fact.
- Mehrab4226
- Posts:230
- Joined:Sat Jan 11, 2020 1:38 pm
- Location:Dhaka, Bangladesh
Re: BdMO Regional 2021 Higher Secondary P8
$16777216$Dustan wrote: ↑Sat Mar 27, 2021 5:08 pmwhat is your ans then?Mehrab4226 wrote: ↑Sat Mar 27, 2021 4:43 pmI didn't think about $f$ could be bijective.
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é
-Henri Poincaré
-
- Posts:194
- Joined:Sat Jan 02, 2021 9:28 pm
Re: BdMO Regional 2021 Higher Secondary P8
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$Mehrab4226 wrote: ↑Sat Mar 27, 2021 4:43 pmI didn't think about $f$ could be bijective.
So it gave me a weird solution, a huge one in fact.
Hmm..Hammer...Treat everything as nail
Re: BdMO Regional 2021 Higher Secondary P8
Me tooAsif Hossain wrote: ↑Sat Mar 27, 2021 9:24 pmyou 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$Mehrab4226 wrote: ↑Sat Mar 27, 2021 4:43 pmI didn't think about $f$ could be bijective.
So it gave me a weird solution, a huge one in fact.