Since $f$ is a function on a finite set, it is eventually periodic, say with period $T$. Select a large $n$ such that $(2n+1)-(n+2)$ is a multiple of $T$, so that \[ f^{n+2} = f^{2n+1} \]Then taking $g = f^n$, we get \[ fgf = gfg \implies f = g = f^n. \]Since $f = f^n$, $f$ is a bijection on $T = f(S)$, as desired. Remark: [Longer motivation] This solution might seem very algebraic, but you can motivate it (or some equivalent solution) by considering a ``generic'' function $f$ and drawing the resulting directed graph. The idea is that if $f(f(S)) \neq f(S)$ then there should exist a function $g \neq f$ such that $gfg = fgf$. The simplest such function might have a picture like in the attachment. It's natural to ask $g$ to preserve the cycle, and if one does so one finds the unique function $g$ which works is the one with $g(1) = x_0$, $g(2) = x_{T-1}$. In general, $f$'s picture consists of several cycles (possibly degenerate with length one or two), and a directed rooted tree growing out of any vertex on a cycle. If we have a cycle $x_0 \to x_1 \to \dots \to x_{T-1} \to x_0$ as in the picture, and an element $y$ of the tree with height $k$ in the tree (the distance from $y$ to the root) then $g(y) = x_{T-(k-1)}$ works fine (indices mod $T$). If any rooted tree has height more than $2$ (equivalently, $f(f(S)) \neq f(S)$) then $g \neq f$, but $gfg = fgf$ by construction.

Beautiful! An excellent problem! But it rather has the flavor of a Putnam problem than that of an IMO problem.

We proceed by contradiction. If we interpret $f$ as a directed graph on the elements of $S$ (where arrows connect $s\to f(s)$), we see that $f(f(S))\neq f(S)$ implies that there exists $s\in f(S)$ whose parents $p_1,\cdots, p_i$ have indegree $0.$ We will now construct a function $g\neq f$ such that $f\circ g\circ f = g\circ f\circ g.$ By applying $f$ repeatedly to $s,$ we must eventually run into a directed cycle, say at $f^{(k)}(s).$ We now define $g=f$ for every element in the cycle, and $g(t)=f^{(k-x)}(t)$ where $t$ is the distance from $t$ to the cycle. It can easily be shown that this works, and moreover $f(p_i) \neq g(p_i)$ for the guy with zero indegree. We may now conclude.

For each $i \geq 1$ let $S_i = f^i(S)$ and $S_0 = S$. Then $S_i \neq \varnothing$ and we have the chain of inclusions $$S_0 \supseteq S_1 \supseteq S_2 \supseteq \dots$$ And because $S_0 = S$ is finite this sequence must eventually stabilize, i.e. there exists a set $Y$ and a positive integer $N$ such that $S_n = Y$ for all $n \geq N$. Restricted to $Y$, $f$ is a bijection, and therefore it can be broken into a product of cycles. Let $P$ be the product of the sizes of these cycles, then $f^P$ is the identity when restricted to $Y$. Choose $k$ sufficiently large such that $kP + 1 \geq N$ and set $g = f^{kP + 1}$. Then we have $$f \circ g \circ f = f^{kP +3} \qquad g \circ f \circ g = f^{2kP + 3}$$ We have $f^{kP + 3}(S) = Y$ by our choice of $Y$ and therefore $f^{2kP + 3}(x) = f^{kP + 3}(x)$ for all $x \in S$, because $f^{kP}$ is the identity function restricted to $Y$. Thus $f \circ g \circ f = g \circ f \circ g$ for this choice of $g$, and the problem condition implies that $f = g$. Therefore $f(S) = g(S) = Y$ by our choice of $g$, and because $f(Y) = Y$ it follows that $f(f(S)) = f(S)$ as desired.

Let $g=f^n$, and assume $f\ne g$. Then, we have $f^{n+2}\ne f^{2n+1}$, so \[f\ne f^n\implies f^{n+2}\ne f^{2n+1}.\]Taking the contrapositive, we see that \[f^{2n+1}=f^{n+2}\implies f=f^n.\]We now show that we can pick $n$ such that $f^{2n+1}=f^{n+2}$. Call $x\in S$ recurring if there exists $a\in S$ such that $a,f(a),f^2(a),f^3(a),\ldots$ contains $x$ infinitely many times. We see that each recurring $x$ has a period under $f$, call it $p(x)$, and let $P$ be the lcm of all the periods of all the recurring elements. Then, we see that $f^P$ is the identity on the set of recurring elements. However, if $m>100|S|$ (to be safe), we see that $f^m(x)$ is recurring by pigeon hole principle (if in the sequence of repeatedly applying $f$ we ever get a repeat, all elements from there on forward are recurring). Thus, we take $n=1+100|S|\cdot P$, so that \[f^{n-1}(f^{n+2}(x))=f^{n+2}(x)\,\,\forall x\in S\], since $f^{n+2}(x)$ is recurring, and $P\mid n-1$. Thus, we have that $f^{n+2}=f^{2n+1}$, so $f=f^n$. Now, we see that $f^{n-1}(f(x))=f(x)$ for all $x\in S$, so $f^{n-1}(x)=x$ for all $x\in T$. If $f(a)=f(b)$, we apply $f^{n-2}$ to both sides to show $a=b$, so $f$ is injective on $T$. Also $f^{n-2}(x)$ is a preimage of $x$ for any $x\in T$, so $f$ is surjective on $T$. Thus, $f$ is bijective on $T$, so $f(T)=T$, as desired. Personal Remark: Looking at v_Enhance's remark, one can see a lot more structure of this problem by looking at the directed graph of $f$. When solving this problem, I noted no such deeper structure; rather, I first saw that $f=f^n$ finishes the problem, and then I simply dropped in $g=f^n$ and blindly followed the problem to this solution.

Tsukuyomi wrote: let $T=f(S)$ be the image of $S$ under $f$. $f(T)=T$. Sorry, I am not too familiar with this notation. What does the above mean? Is it just the set of all x s.t. there exists y s.t. f(y)=x?

A bit less technically worded solution, although the idea is the same: Let us suppose $f(T) \neq T$. Then, $f^k$ and $f$ have different range for $k > 1$, thus $f^k \neq f$. As $S$ is finite, we can partition the natural numbers into a finite number of equivalence classes, where $i$ and $j$ are in the same class iff $f^i = f^j$. Atleast one of these equivalence class must have an infinite number of members, thus there exist $a,b > 1$ such that $2a - 1 \leq b$, for which there will exist non-negative integer $n$ such that $2a + 2n + 1 = b + n + 2$. As $f^{a+n} = f^{b+n}$, $g = f^{a+n}$ gives the required contradiction.

Construct the directed graph $S\to S$ determined by $f$. Given $s\in S$, let $k$ be the minimum nonnegative integer such that $f^k(s)$ is in a directed cycle. Call $f^k(s)$ the stem, $k$ its order, and the cycle it is in the root of $s$. Then, consider the function $g$ which brings $s$ to the element which is $\text{order}-1$ away from the stem, going along the root, but in the opposite direction. It is not hard to see that $f\circ g\circ f=g\circ f\circ g$, so we must have $f=g$. However, $f(s)=g(s)$ iff the stem of $s$ is $s$ itself, or $f(s)$, so all elements in $f(S)$ are already in directed cycles, implying $f(T)=T$.

v_Enhance wrote: Since $f$ is a function on a finite set, it is eventually periodic, say with period $T$. Select a large $n$ such that $(2n+1)-(n+2)$ is a multiple of $T$, so that \[ f^{n+2} = f^{2n+1} \]Then taking $g = f^n$, we get \[ fgf = gfg \implies f = g = f^n. \]Since $f = f^n$, $f$ is a bijection on $T = f(S)$, as desired. Remark: [Longer motivation] This solution might seem very algebraic, but you can motivate it (or some equivalent solution) by considering a ``generic'' function $f$ and drawing the resulting directed graph. The idea is that if $f(f(S)) \neq f(S)$ then there should exist a function $g \neq f$ such that $gfg = fgf$. The simplest such function might have a picture like in the attachment. It's natural to ask $g$ to preserve the cycle, and if one does so one finds the unique function $g$ which works is the one with $g(1) = x_0$, $g(2) = x_{T-1}$. In general, $f$'s picture consists of several cycles (possibly degenerate with length one or two), and a directed rooted tree growing out of any vertex on a cycle. If we have a cycle $x_0 \to x_1 \to \dots \to x_{T-1} \to x_0$ as in the picture, and an element $y$ of the tree with height $k$ in the tree (the distance from $y$ to the root) then $g(y) = x_{T-(k-1)}$ works fine (indices mod $T$). If any rooted tree has height more than $2$ (equivalently, $f(f(S)) \neq f(S)$) then $g \neq f$, but $gfg = fgf$ by construction. Why is \[ fgf = gfg \implies f = g = f^n. \]?

@above $fgf = gfg$ directly follows from $f^{n+2} = f^{2n+1}$ (as $fgf = f^{n+2}$, $gfg = f^{2n+1}$). We know $f \neq g \implies fgf \neq gfg$ so taking the contrapositive gives us $fgf = gfg \implies f = g$.

Solution with stroller. View $f$ as a directed graph on $S$. Suppose $f(f(S))\ne f(S)$. We construct some $g\ne f$ with $f\circ g \circ f = g\circ f \circ g$. We are given that, for some $t$ and $k \ge 2$, we have $t\rightarrow f(t) \rightarrow \cdots \rightarrow f^k(t)$ such that iterative applications of $f$ to $f^k(t)$ create a cycle and $k$ is minimal. Additionally, we can assume that $t\not\in f(S)$. Fix this $t$. We will now construct a working $g$. Let $S' \subseteq S$ be the set $\{f^n(t)\mid n \in \mathbb{Z}_{\ge 0}\}$. We will operate on $S'$; just let $g=f$ for $t' \not\in S'$. Now, define the following things; let $d$ be the minimal positive integer with $f^{k+d}(t) = f^{k}(t)$. Define $x_n = f^{n+k-3}(t)$ for any integer $n$ with $n+k-3\ge 0$. Note that $x_{n+k} = x_n$ for any $n > 2$. Let $g$ be $f$ except take $g(x_i) = x_{d+3-i+kd}$. Graphically, we are mapping the $x_i$ at or before $x_1$ to the directed cycle from $f^k(t)$ to $f^{k+d}(t)$. It is clear that $g\circ f \circ g$ is $f\circ g\circ f$ for $i >1$. It is clear that $g$ will have $f\circ g\circ f (x_i)=g\circ f\circ g(x_i)$ for $i\le 0$ because we will end up mapping to the cycle. Thus, it suffices to check that \[g(f(g(x_1)))=g(f(x_{d+2}))=g(x_3)=x_4=f(x_3)=f(g(x_2))=f(g(f(x_1))),\]which is indeed true. $\fbox{}$

ILLUSTRATION. $\mathcal{YUH}$.

blawho12 wrote: @above $fgf = gfg$ directly follows from $f^{n+2} = f^{2n+1}$ (as $fgf = f^{n+2}$, $gfg = f^{2n+1}$). We know $f \neq g \implies fgf \neq gfg$ so taking the contrapositive gives us $fgf = gfg \implies f = g$. Gotcha! Thanks

Tell me if something is wrong! Let $T=\{x_1,x_2,...,x_i\}$. We must prove that $f:\{x_1,x_2,...,x_i\}\rightarrow \{x_1,x_2,...,x_i\}$ is bijective. Lemma: $f(a)\neq a$ for any $a \in \{x_1,x_2,...,x_i\}$. Proof: Take a function $g$, such that $g(a)=a$ and $g \neq f.$ $$f(g(f(a)))=a=g(f(g(a)))$$WLOG $f(x_1)=f(x_2)=x_k$ where $k \ge 3.$ Take a function $g$, such that $g(x_j)=x_k$ for all $j\neq k$ and $g(x_k)=x_1$ or $g(x_k)=x_2$ One of the 2 functions is distinct from $f$. And easy to check that $f(g(f(x_1)))=g(f(g(x_1)))$ or for $x_2$.

Wow. This was fun! I'm not quite sure of my solution. Someone please check it please

A-Thought-Of-God wrote: Wow. This was fun! I'm not quite sure of my solution. Someone please check it please

Are you sure that $g$ works? When I plug $x=m$ in $f(g(f(x))=g(f(g(x)))$, I get $f(f(f(m))=f(f(m))$, which isn't true.

Really funny problem. Note that for all sufficiently large $m$, there exists $n \in \mathbb{N}$ such that $f^{m + n} = f^m$ since $f: S \to S$ on finite sets. Therefore, take large $m$ such that $n \mid m - 1$. Therefore, taking $g = f^m$, we have \[ f^{m + 2} = f \circ g \circ f = g \circ f \circ g = f^{2m + 1} \]This is true since $f^{2m + 1} = f^{m + 2} \circ f^{m - 1} = f^{m + 2}$, contradicting the statement unless $f^m = f$, however we are done, as this means $f^{a}(S) \subset f^{b} (S)$ when $a \le b$.

ISL 2017 A3 wrote: Let $S$ be a finite set, and let $\mathcal{A}$ be the set of all functions from $S$ to $S$. Let $f$ be an element of $\mathcal{A}$, and let $T=f(S)$ be the image of $S$ under $f$. Suppose that $f\circ g\circ f\ne g\circ f\circ g$ for every $g$ in $\mathcal{A}$ with $g\ne f$. Show that $f(T)=T$. Solution.(Solved with Geometry6) Suppose that $f=f^k\implies f(S)=f^k(S)\implies f(S)=f^2(S)$, which clearly isn't true$\implies f\neq f^k$ $$g=f^k\implies f^{2k+1}=f\circ g\circ f\ne g\circ f\circ g=f^{k+2}\implies f^{k+2}\neq f^{2k+1}$$(WLOG) $a>b$ Claim 1:There $\exists a,b$ such that $f^a=f^b$ Proof: It is clear there the set $A$ is finite thus we get that $\{f,f^2,...\}$ is also finite thus by pigeonhole we have that there exists such $a,b.\square$ (Note that (WLOG)we have a-b can be big enough). Claim 2: $f^t\neq f^{t+k-1} \forall t<k+2$ Proof: if this is not true let $f^a=f^{a+k-1}$ we have that $=f^{k+2-t}f^{t}\neq f^{k+2-t}f^{t+k+1} \Rightarrow\Leftarrow$ note that now we have that by claim 2 we get that $f^a \neq f^b \Rightarrow \Leftarrow.\blacksquare$

It's well-known that $f$ is eventually periodic. Because of this, there must exist a large multiple $N$ of the period such that $f^{M}(x)=f^{M+N}(x)$ for all $M\ge N$. Now, take $g=f^{N+1}$; the LHS is equal to $f(f^{N+2})=f^{N+3}$, while the RHS is equal to $f^{N+1}(f^{N+2})=f^{2N+3}=f^{N+3}$. From here, we can see that it's necessary that $f^{N+1}=f$ because otherwise, we can set $g=f^{N+1}$, which means that $f^N$ is the identity on $T$ and $f$ therefore necessarily is a bijection on $T$.

View $f$ as a directed graph $G$ where $S$ is the vertex set and $x$ points to $f(x)$. If $G$ is disconnected, split it into connected sub-components and induct down, hence suppose $G$ is connected. Also ignore the definition of $T$ in the problem. Claim: There exists exactly one cycle in $G$. Proof: If $G$ is a tree, by inducting on the distance of a vertex from the nearest leaf, we find that each edge must be oriented in a direction "away" from the leaves (so if $u \to v$, $u$ is farther from a leaf than $v$ is), but this is absurd. If $G$ has at least one cycle, then inducting from the distance from an arbitrary cycle yields that if $u \to v$, then $u$ is farther from that cycle than $v$ is, which yields a contradiction if we have another cycle (one of the vertices on the cycle would need to have outdegree two). Thus the structure of $G$ is a directed cycle $C$, and a number of trees rooted at some vertex of the cycle whose edges point "towards" the cycle. If $f(f(S)) \neq f(S)$, this means that there exists some tree $T$ with height at least $2$. Suppose $C$ is of the form $$x_1 \to x_2 \to \ldots \to x_k \to x_1,$$where WLOG $T$ is rooted at $x_1$ and indices are taken modulo $k$. Now define $g$ as satisfying $g \equiv f$ over $G \setminus T$, and if $x \in T$ and is distance $d$ from $C$, let $g(x)=x_{2-d}$. Clearly, $f \not \equiv g$. For $x \in G \setminus T$, we evidently have $f(g(f(x)))=g(f(g(x)))$. If $x \in T$ has distance $d$ from $C$, $f(x)$ has distance $d-1$ (possibly zero) from $C$, then $g(f(x))=x_{3-d}$ and $f(g(f(x)))=x_{4-d}$. Further, $g(x)=x_{2-d}$, so $f(g(x))=x_{3-d}$ and $g(f(g(x)))=x_{4-d}$. Hence $f \circ g \circ f \equiv g \circ f \circ g$. This implies the contrapositive of the statement: if $f(f(S)) \neq f(S)$, some function $g$ exists such that $f \circ g \circ f \equiv g \circ f \circ g$, so we're done. $\blacksquare$

Let's take $S=\{1,2,\cdots, n\}$. Let $I_j$ be image of $f^j$. Obviously, $I_{j+1}\subseteq I_{j}$, so there is $M\in\mathbb{N}$ such that $I_m=I_{m+1}$ for all $m\geq M$ and let this constant images be $\{a_1,a_2,a_3,\cdots,a_k\}$. So we have $$\{f^m(1),\cdots, f^m(n)\}=\{a_1,a_2,\cdots,a_k\}$$$$\{f^{m+1}(1),\cdots,f^{m+1}(n) \}=\{f(a_1),f(a_2),\cdots f(a_k)\}=\{a_1,a_2,\cdots, a_k\}$$for all $m\geq M$. So we get for all $i=1,2,\cdots, k$ there is $r_i$ such that $f^{r_i}(a_i)=a_i$. Now take $g=f^{N+1}$ where $N\geq M$ and $lcm(r_1,r_2,\cdots, r_k)\mid N$. So we have $g\circ f \circ g = f^{2N+3}=f^N(f^{N+3})=f^{N+3}=f\circ g \circ f$, which means $f=g=f^{N+1}$. So we get $S\subseteq f^2$, which gives $f(T)=T$, as desired.

Since $S$ is finite $f$ has some period $n;$ take $m>n$ such that $n|(m-1)=(2m+1)-(m+2)$ and put $g=f^{(m)}$ so $$f\circ g\circ f=f^{(m+2)}=f^{(2n+1)}=g\circ f\circ g\implies f=g.$$Thus we finally obtain that $f(S)=f^{(m)} (S)$ and so $f$ is a bijection on $T$ as desired.

Since there are finitely many functions from $S$ to $S$, there are $a,b$ such that $f^a = f^{a+b}$. So for all large $m$, $f^m = f^{m+b}$ This implies that there exists $k$ (say, $k=ab$) such that $f^{2k} = f^k$. Now I claim that $f^{k+1} = f$. Suppose not and take $g = f^{k+1}$. \[\implies f^{k+3} \ne f^{2k+3}.\]However, \[f^{2k+3} = f^3(f^{2k}) = f^3(f^k) = f^{k+3}.\]A contradiction. So $f$ is a bijection on $T$, because $f^k(T)\subset T$ and $|f^k(T)| = |T|$.

Solved with GoodMorning. Suppose that $f(f(S)) \ne f(S)$. Notice that for any $x\in S$, repeatedly applying $f$ to $S$ at some point runs into a cycle of $f$ due to $S$ being finite. Let $d$ denote the lcm of all cycles of $f$. This implies that $f^d(x) = x$ for all $x$ in a cycle of $f$. This can be extended to $f^{kd}(x) = x$ for all positive integers $k$. Choose $n > 1434 |S| + 1000$ such that $d$ divides $(2n+1) - (n+2) = n - 1$. Claim: $f\ne f^n$. Proof: If $f = f^n$, then notice that $f(x)$ must be in a cycle of $f$ for any $x\in S$. This implies that if $a\in f(S)$, then since $a$ is in a cycle, we have $a\in f(f(S))$. Obviously anything in $f(f(S)) $ is also in $f(S)$, so we have $f(S) = f(f(S))$, contradiction. $\square$ Setting $g = f^n$ gives that $f \circ g\circ f = f^{n+2}$ and $g\circ f\circ g = f^{2n+1}$. Now, notice that $f^{2n+1} = f^{n-1}(f^{n+2})$. Since $f^{n+2}$ is in a cycle of $f$ (this follows due to setting $n$ large) and $n-1 = kd$ for some positive integer $k$, $f^{2n+1} = f^{n+2}$, contradiction.

Clearly, image of $f$ cannot have any elements outside of $T$, so $f^k(S)\subseteq T$. Note that since $S$ is finite, $f$ is eventually periodic. Suppose the period is $n$ and $f\neq f^{kn+1}$ for some large enough $k$ then \[f\circ f^{kn+1} \circ f = f^{kn+3} = f^{2kn+3} = f^{kn+1} \circ f \circ f^{kn+1}\]which is a contradiction. Therefore, $f=f^{kn+1}$ for all large enough $k$. Note that $f^{kn}\subseteq T$, and $f^{kn+1}=f=T$. Since $f(f^{kn})=T$, for each $y\in T$ it is known that there exists $x\in f^{kn}\implies x\in T$ such that $f(x)=y$ so $f(T)=T$.

Construct the directed graph on $S$ where for each $t \in S$, an edge $t \rightarrow f(t)$ is placed. For $s\in S$, let $k$ be the minimum nonnegative integer such that $f^k(s)$ is in a directed cycle. Let $g$ be the function that takes $s$ to the element that has distance $k-1$ from $f^k(s)$. It can be easily seen that $f\circ g\circ f=g\circ f\circ g$, so the problem condition implies $f=g$. Note that $f(s)=g(s)$ if and only if $f^k(s)=s$, so all elements in $T$ are in directed cycles by applying this to all $s \in S$, from which $f(T)=T$.

We will prove the contrapositive, that is, if $f(T)\ne T$ we will construct a function $g$ that has $f\circ g\circ f\equiv g\circ f\circ g$. Construct the arrows graph of $f$ and consider the connected components. Each must be a cycle, possibly with some trees sticking out of it. Then let $g(x)=f(x)$ for all $x$ on the cycle, let $g(x)$ for $x$ on a tree leading into the cycle be the $y$ on the cycle such that $f^{n+1}(x)=f^{n}(y)$ for all large $n$(since the tree must lead into the cycle so this must exist). Clearly $f\circ g\circ f\equiv g\circ f\circ g$. Note that there must be at least one cycle that has at least one non-singleton tree sticking out of it(if none of these exist, $f(T)=T$, contradiction), so the image of $g$ does not contain the full image of $f$, so $f\ne g$. $\blacksquare$

Suppose otherwise. Then consider the directed graph on $f$, and say it has some maximal cycle $v_1, v_2, \dots, v_k$. Then the graph $G$ can be characterized as a series of directed trees pointing into this cycle. Now assume that some of the trees have more than one edge, i.e. the desired condition is not true. Then, we may construct a valid function $g$ as follows: for any tree $T$ rooted at $v_i$ along the cycle, point $g$ from $v \in T$ to $v_{i+d-1}$, where $d$ is the distance from $v$ to $v_i$ in $T$. This preserves the condition, thus contradiction.

My solution is very similar to those above, so I'll provide only a very cursory explanation Assume that there exists some $t \in f(S)$ such that $t \notin f(f(S))$ Converting this problem into a directed graph, it is apparent that point $t$ must be a leaf in a branch connected to a cycle. Label the points of the cycle $a_1$, $a_2$, $\ldots$, $a_n$, where the branch containing $t$ is connected to $a_1$ Let function $g$ be a replica of $f$ except for the fact that for all elements in the branch containing $t$, if $d(p)$ denotes the least distance from that point to the cycle then point $p$ is reconnected to point $a_{2-d(p)}$ $g$ satisfies $fgf = gfg$, causing a contradiction

It suffices to provide a construction for $g(x) \neq f(x)$ such that $g(f(g(x))) = f(g(f(x)))$ if $f(T) \neq T$. For each $x$, here is how we define $g(x)$: let $k$ be the number of vertices in the component containing $x$ and let $\ell$ be the length of the cycle in the component containing $x$. \[ g(x) = f^{n+1} (x), \]where $n$ is the smallest multiple of $\ell$ greater than $k$. Note that this value of $n$ only depends on the component that $x$ belongs to and nothing more. To verify this construction works: we need to check that \[ f^{n+3} (x) = f^{2n+3} (x)\]for all $x$ (and the definitions of $n$ based on each $x$). But this is true since $f^{n+3} (x)$ is in the cycle by the definition of $n$, and $n$ is a multiple of the length of the cycle.

Funny problem. Since there are finitely many functions $S \to S$, so by infinite pigeonhole principle, there exist $k, l$ such that $f^k = f^l$. Moreover, we can choose $k, l$ such that $k - l$ is large enough. Thus if we let $t = k-l+1$, then we get $f^{2t+1} = f^{t+2}$. Now if $f \neq f^t$, then we have $f \circ f^t \circ f \neq f^t \circ f \circ f^t$, or equivalently $f^{2t+1} \neq f^{t+2}$, a contradiction. Hence $f = f^t$, so $f(S) = f^t(S)$. Since $f^n(S)$ is subset of $f^{n-1}(S)$ for all $n$, hence we get $f(f(S)) = f(S)$. Therefore we're done. $\blacksquare$

Great problem. Given a set $X$ and a function $f$, we denote by $\textrm{Im}_Xf$, the image of $X$ under $f$. First, we observe that $\textrm{Im}_Sf^{k+1}$ is always contained in $\textrm{Im}_Sf^k$ Hence, whenever the sets $\textrm{Im}_Sf^k$ and $\textrm{Im}_Sf^{k+1}$ are different, we have $|\textrm{Im}_Sf^{k+1}| < |\textrm{Im}_Sf^k|$. Paired with the fact that $S$ is a finite set, this implies that the set $\textrm{Im}_Sf^k$ is the same for all sufficiently large integers $k$. Let this set be $H=\{a_1, a_2, \dots, a_n\}$. Since $f(H)=H$, $f$ must be bijective in $H$. Hence, there must exist positive integers $b_1, b_2, \dots, b_n$ such that $f^{b_i}(a_i)=a_i$ for all $1 \leq i \leq n$. Now, suppose for contradiction that $f(T) \neq T$. For the sake of convenience, we let $s=pb_1b_2 \dots b_n$ for some large enough positive integer $p$. Then, since $s$ is sufficiently large, we have $\textrm{Im}_Sf^{s+3} = H$ and hence $f^{s+3}(x)=f^{2s+3}(x)$ for all $x \in S$. Also, since $|\textrm{Im}_Sf^{s+3}| = |H| < |T| = \textrm{Im}_Sf$, we must have $f^{s+3} \neq f$. Finally, picking $g = f^{s+3}$ we obtain $f \circ g \circ f = f^{s+3} = f^{2s+3} = g \circ f \circ g$, a contradiction. $\blacksquare$

Feels more combo? Suppose $f(T) \neq T$. This implies that $f \neq f^n$ for all $n$ since they have different ranges. However, note that $f$ is eventually periodic , say with period $k$. Thus taking $g=f^n$ for a sufficiently large $n$ with $k\mid n-1$ we see the LHS is $f^{2n+1}$ and the RHS is $f^{n+2}$ which are equal.