Nemotron-IMO-Bench 2026 C4

Let $n$ be a positive integer and let $S_n$ (respectively $T_n$) be the set of all bijections (respectively all maps) from $[n]:=\{1,\ldots, n\}$ to $[n]$. For $\tau\in T_n$ let ${\rm ord}(\tau)$ be the number of distinct maps in the set $\{\tau, \tau \circ \tau, \tau \circ \tau \circ \tau, \ldots\}$, where o denotes composition. Prove that for sufficiently large $n$ $$g(n)=\max _{\tau \in T_n} \operatorname{ord}(\tau)<\max _{\tau \in S_n} \operatorname{ord}(\tau)+n^{0.501}.$$