International Mathematics Competition
for University Students
2025

IMC2025: Day 1, Problem 5

Problem 5. For a positive integer \(\displaystyle n\), let \(\displaystyle [n]=\{1,2,\ldots,n\}\). Denote by \(\displaystyle S_n\) the set of all bijections from \(\displaystyle [n]\) to \(\displaystyle [n]\), and let \(\displaystyle T_n\) be the set of all maps from \(\displaystyle [n]\) to \(\displaystyle [n]\). Define the order \(\displaystyle \operatorname{ord}(\tau)\) of a map \(\displaystyle \tau\in T_n\) as the number of distinct maps in the set \(\displaystyle \{\tau,\tau\circ \tau, \tau\circ \tau\circ \tau,\ldots\}\) where \(\displaystyle \circ\) denotes composition. Finally, let

\(\displaystyle f(n) = \max_{\tau\in S_n}\,\operatorname{ord}(\tau) \quad\text{and}\quad g(n) = \max_{\tau\in T_n}\,\operatorname{ord}(\tau) . \)

Prove that \(\displaystyle g(n)<f(n)+n^{0.501}\) for sufficiently large \(\displaystyle n\).

Fedor Petrov, St Petersburg State University

Solution. For every \(\displaystyle \tau \in T_n\) we need to prove that \(\displaystyle \operatorname{ord}(\tau)\leqslant f(n)+n^{0.501}\) (if \(\displaystyle n\) is large enough). Denote by \(\displaystyle C(\tau)\) the set of elements \(\displaystyle x\in [n]\) for which \(\displaystyle \tau^{k}(x)=\underbrace{\tau(\ldots\tau}_k(x)\ldots)=x\) for some \(\displaystyle k>0\). It is immediate that \(\displaystyle C(\tau)\) is a \(\displaystyle \tau\)-invariant set; let \(\displaystyle \tau_c=\tau|_{C(\tau)}\), that is a permutation on \(\displaystyle C(\tau)\).

Let \(\displaystyle N\) be the order of this permutation \(\displaystyle \tau_c\), clearly \(\displaystyle N\leqslant g(n)\). Consider an arbitrary element \(\displaystyle x\in [n]\setminus C(\tau)\). The sequence \(\displaystyle x,\tau(x),\tau^{2}(x),\ldots\) is eventually periodic, but not from the beginning, because \(\displaystyle x\notin C(\tau)\).

Let \(\displaystyle h(x)>0\) be the minimal number for which \(\displaystyle \tau^{h(x)}(x)\) is in the period; equivalently, this is the minimal number for which \(\displaystyle \tau^{h(x)}(x)\in C(\tau)\). Let \(\displaystyle R=\max\limits_{x\in [n]\setminus C(\tau)} h(x)\). Note that \(\displaystyle \tau^{R}(x)=\tau^{R+N}(x)\) for all \(\displaystyle x\in [n]\), since \(\displaystyle \tau^R(x)\in C(\tau)\) for all \(\displaystyle x\in [n]\). Therefore, \(\displaystyle \operatorname{ord}(\tau)\leqslant N+R\). Thus, if \(\displaystyle R<n^{0.501}\), we are done.

Now assume that \(\displaystyle R\geqslant n^{0.501}\), that is, \(\displaystyle h(x)\geqslant n^{0.501}\) for some \(\displaystyle x\notin C(\tau)\). It yields \(\displaystyle |C(\tau)|\leqslant n-n^{0.501}\). Consider the cycle lengths of the permutation \(\displaystyle \tau_c\). We claim that there exists a prime number \(\displaystyle p<n^{0.501}\) which does not divide any of these lengths. Indeed, otherwise the sum of cycle lengths of \(\displaystyle \tau_c\) is not less than the sum of all prime numbers not exceeding \(\displaystyle n^{0.501}\) (because each positive integer is not less than the sum of its prime divisors, that in turn follows from \(\displaystyle ab\geqslant a+b\) for \(\displaystyle a,b\geqslant 2\)). But for large \(\displaystyle n\), the number of prime numbers less than \(\displaystyle n^{0.501}\) is at least \(\displaystyle n^{0.5009}\) by some weak version of Prime Number Theorem (that also has many short proofs). Therefore, their sum exceeds \(\displaystyle n\), contradiction.

Now we may consider the permutation \(\displaystyle \tau_0\in S_n\) which acts as \(\displaystyle \tau_c\) on \(\displaystyle C(\tau)\) and has a cycle of length \(\displaystyle p\) on \(\displaystyle [n]\setminus C(\tau)\). The order of \(\displaystyle \tau_0\) is not less than \(\displaystyle p\cdot N\), therefore \(\displaystyle N\leqslant f(n)/p\leqslant f(n)/2\), and by the above argument we get \(\displaystyle \operatorname{ord}(\tau)\leqslant N+R\leqslant f(n)/2+n<f(n)\) for large \(\displaystyle n\).