Let $A=\{1,2,3,...,9\}$ and $f:A \rightarrow A$ is a bijection such that $(fofofo\cdots n$ times) $=f$ but others are not identical to $f$

Question

Let $\mathrm{A}=\{1,2,3,...,9\}$ and $f:\mathrm{A \rightarrow A}$ is a bijection such that $(fofofo\cdots n$ times) $=f$ but $(fof),(fofof), \cdots, (fofofo\cdots (n-1)$ times) are not identical to $f$. Then largest value of $n$ is?

Answer given- 21

I thought of taking an apt function and getting the answer, but answer seems out of range, any hint?

Answer 1

The following answer is quite rough, and assume some acquaintance with permutation groups.

You can write $\{1,\dots,9\}$ as a disjoint union of cycles for $f$. For example, if $f(1)=3,f(3)=4,f(4)=1$, then $(1\,3\,4)$ is such a cycle, and we say its length is $3$. Then you can check that the smallest number $n>0$ such that $f^{\circ n}=\mathrm{id}_{\{1,\dots,9\}}$ is the least common multiple of the length of its cycles. From all the partition of $9$ (e.g. $(1,1,7),(2,2,2,3),\dots$), you can check that $(4,5)$ is the one maximizing this least common multiple, this latter being equal to $20$. Finally, since you want the smallest number $n>1$ such that $f^{\circ n}=f$, you have to add $1$ to $20$, thus leading to $21$.

Answer 2

Note that if $f^{(n)} = f\circ ...\circ f = f$ then the order of $f$ is $n-1$. So the problem reduces to find the permutation of $S_9$ with the maximum order. Write the permutation as a product of $k$ disjoint cycles. We would like to maximize the least common multiple of the product of those cycles' length. If the length of the largest cycle is six, then answer is six since it will be a multiple of the other cycles' length. If it is seven then the answer is $max(lcm(7,1,1), lcm(7,2)) = 14$ and if it is 8 or 9 then the answer is 8 or 9 respectively. Now, if the size is five the answer is $max(lcm(5,4), lcm(5,3,1)), lcm(5,2,2)) = 20$. Finally, if the size of largest cycle is no more than four the answer is no more than $lcm(4,3,2,1) = 12$. So the maximum order is 20 and thus $n = 21$ is the answer.

An example of such an $f$:

$$ f(1) = 2 \\ f(2) = 3 \\ f(3) = 4 \\ f(4) = 5 \\ f(5) = 1 \\ f(6) = 7 \\ f(7) = 8 \\ f(8) = 9 \\ f(9) = 6 $$.

Answer 3

Hints : We can think $f$ as permutation i.e, all cycles of symmetric group $S_9$.

Now just try to find the highest order cycle.

It's the easier way , I think!