BdMO Regional 2021 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
Pro_GRMR
Posts:46
Joined:Wed Feb 03, 2021 1:58 pm
BdMO Regional 2021 Secondary P8

Unread post by Pro_GRMR » Mon Mar 29, 2021 1:54 am

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

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

Re: BdMO Regional 2021 Secondary P8

Unread post by Pro_GRMR » Mon Mar 29, 2021 10:09 pm

Pro_GRMR wrote:
Mon Mar 29, 2021 1:54 am
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$.
  1. Observe that,
    $f(x)-x\equiv0\pmod{3}$
    $\Longleftrightarrow f(x)\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 injective and surjective. So, $f$ is bijective.
Now 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 the same class if and only if $x\equiv y\pmod{3}$
In the set $S_1$, we have $f(1),f(4),f(7),f(10)\in\{1,4,7,10\}$ with $10$ possibilities :
  • One where $f(x)=x$
    1. $f(1)=1, f(4)=4, f(7)=7, f(10)=10$
  • Six where two are such that $f(x)=x$ and the two other map on each other
    1. $f(1)=1, f(4)=4, f(7)=10, f(10)=7$
    2. $f(1)=1, f(4)=10, f(7)=7, f(10)=4$
    3. $f(1)=1, f(4)=7, f(7)=4, f(10)=10$
    4. $f(1)=10, f(4)=4, f(7)=7, f(10)=1$
    5. $f(1)=7, f(4)=4, f(7)=1, f(10)=10$
    6. $f(1)=4, f(4)=1, f(7)=7, f(10)=10$
  • Three where none is such that $f(x)=x$ (just split set in pairs).
    1. $f(1)=4, f(4)=1, f(7)=10, f(10)=7$
    2. $f(1)=7, f(4)=10, f(7)=1, f(10)=4$
    3. $f(1)=10, f(4)=7, f(7)=4, f(10)=1$
And the same goes for $S_2= \{2,5,8,11\}$ and $S_3= \{3,6,9,12\}$

And so we get a total of $10*10*10=\boxed{10^3}$ such functions for $3$ such sets.

Note: Some parts we directly inspired by Anindya Biswas's post in this thread and pco's post in this thread.
Also, visit this if you're having trouble understanding.
"When you change the way you look at things, the things you look at change." - Max Planck

Paradox Paul
Posts:1
Joined:Tue Feb 16, 2021 11:26 am

Re: BdMO Regional 2021 Secondary P8

Unread post by Paradox Paul » Wed Mar 31, 2021 9:41 pm

Why the answer is 10³?(I mean why did you multiply the number 10 for three times?)

mijanur
Posts:1
Joined:Thu Apr 01, 2021 10:54 am

Re: BdMO Regional 2021 Secondary P8

Unread post by mijanur » Thu Apr 01, 2021 11:00 am

shouldn't the ans be 3*8*8 ?

In the 3 sets there are 4 column. and there are 3 ways to select two of them(as rest two is automatically selected). again there are 8 possible ways to select the numbers between the two column to satisfy the condition . so ans should be 3*8*8. (Third 8 is for the rest two column).

Ok I got it . I thought the ques be not divisible by 3 :)....You are right .It is 10*10810.
Last edited by mijanur on Fri Apr 02, 2021 7:56 pm, edited 1 time in total.

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

Re: BdMO Regional 2021 Secondary P8

Unread post by Pro_GRMR » Thu Apr 01, 2021 10:52 pm

Paradox Paul wrote:
Wed Mar 31, 2021 9:41 pm
Why the answer is 10³?(I mean why did you multiply the number 10 for three times?)
Combinatorics might help you. We have 3 sets, each with 10 possibilities. If we make a tree, it's like a coin flip but with ten sides instead of 2. That would mean we need to multiply all such possibilities for 3 such sets. And so we get $10 \times 10 \times 10 = \boxed{10^3}$
"When you change the way you look at things, the things you look at change." - Max Planck

Post Reply