Taiwan IMO Selection Camp

For $n \ge 1$, denote the $n$-th composition of $f$ with itself by
$$f^n \stackrel{\text{def}}{=} f \circ f \circ \dots \circ f.$$
By hypothesis, if $g \in \mathcal{A}$ satisfies $f \circ g \circ f = g \circ f \circ g$, then $g = f$. A natural idea is to try to plug in $g = f^n$ for some $n$ in the expression $f \circ g \circ f = g \circ f \circ g$ in order to get $f^n = f$, which solves the problem:

Claim: If there exists $n \ge 3$ such that $f^{n+2} = f^{2n+1}$, then the restriction $f: T \to T$ of $f$ to $T$ is a bijection.

Proof. Indeed, by hypothesis,
$$f^{n+2} = f^{2n+1} \Leftrightarrow f \circ f^n \circ f = f^n \circ f \circ f^n \Rightarrow f^n = f.$$
Since $n-2 \ge 1$, the image of $f^{n-2}$ is contained in $T = f(S)$, hence $f^{n-2}$ restricts to a function $f^{n-2}: T \to T$. This is the inverse of $f: T \to T$. In fact, given $t \in T$, say $t = f(s)$ with $s \in S$, we have
$$t = f(s) = f^n(s) = f^{n-2}(f(t)) = f(f^{n-2}(t)).$$
i.e., $f^{n-2} \circ f = f \circ f^{n-2} = \text{id on } T$
(here id stands for the identity function). Hence, the restriction $f: T \to T$ of $f$ to $T$ is bijective with inverse given by $f^{n-2}: T \to T$.

It remains to show that $n$ as in the claim exists. For that, define
$$S_m \stackrel{\text{def}}{=} f^m(S) \quad (S_m \text{ is the image of } f^m).$$
Clearly the image of $f^{m+1}$ is contained in the image of $f^m$, i.e., there is a descending chain of subsets of $S$
$$S \supseteq S_1 \supseteq S_2 \supseteq S_3 \supseteq S_1 \supseteq \dots$$
which must eventually stabilise since $S$ is finite, i.e., there is a $k \ge 1$ such that
$$S_k = S_{k+1} = S_{k+2} = S_{k+3} = \dots \stackrel{\text{def}}{=} S_\infty.$$
Hence $f$ restricts to a surjective function $f : S_\infty \to S_\infty$, which also bijective since $S_\infty \subseteq S$ is finite. To sum up, $f : S_\infty \to S_\infty$ is a permutation of the elements of the finite set $S_\infty$, hence there exists an integer $r \ge 1$ such that $f^r = \text{id}$ on $S_\infty$ (for example, we may choose $r = |S_\infty|$!). In other words,
$$f^{m+r} = f^m \text{ on } S \text{ for all } m \ge k. \qquad (1)$$
Clearly, Eq. (1) also implies that $f^{m+tr} = f^m$ for all integers $t \ge 1$ and $m \ge k$. So, to find $n$ as in the claim and finish the problem, it is enough to choose $m$ and $t$ in order to ensure that there exists $n \ge 3$ satisfying
$$\left\{ \begin{array}{l} 2n + 1 = m + tr \\ n + 2 = m \end{array} \right. \Leftrightarrow \left\{ \begin{array}{l} m = 3 + tr \\ n = m - 2. \end{array} \right.$$
This can be clearly done by choosing $m$ large enough with $m \equiv 3 \pmod r$. For instance, we may take $n = 2kr + 1$, so that
$$f^{n+2} = f^{2kr+3} = f^{4kr+3} = f^{2n+1}$$
where the middle equality follows by Eq. (1) since $2kr + 3 \ge k$.