BdMO Online Forum

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

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.

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

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.

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