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