uniolympiads Ελληνικά

IMC 2025, Day 1, Problem 5

For a positive integer nn, let [n]={1,2,…,n}[n] = \{1, 2, \dots, n\}. Denote by SnS_n the set of all bijections from [n][n] to [n][n], and let TnT_n be the set of all maps from [n][n] to [n][n]. Define the order ord⁡(τ)\operatorname{ord}(\tau) of a map τ∈Tn\tau \in T_n as the number of distinct maps in the set {τ,τ∘τ,τ∘τ∘τ,… }\{\tau, \tau \circ \tau, \tau \circ \tau \circ \tau, \dots\} where ∘\circ denotes composition. Finally, let

f(n)=max⁡τ∈Snord⁡(τ)andg(n)=max⁡τ∈Tnord⁡(τ).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 g(n)<f(n)+n0.501g(n) < f(n) + n^{0.501} for sufficiently large nn.

Original from the official PDFFor a positive integer n, let [n] = {1, 2, . . . , n}. Denote by S n the set of all bijections from [n] to [n], and let T n be the set of all maps from [n] to [n]. Define the order ord(τ ) of a map τ ∈ T n as the number of distinct maps in the set {τ, τ ◦ τ, τ ◦ τ ◦ τ, . . .} where ◦ denotes composition. Finally, let f (n) = max ord(τ ) and g(n) = max ord(τ ). τ ∈S n τ ∈T n Prove that g(n) < f (n) + n 0.501 for sufficiently large n.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(proposed by Fedor Petrov, St Petersburg State University)

Solution. For every τ∈Tn\tau \in T_n we need to prove that ord⁡(τ)⩽f(n)+n0.501\operatorname{ord}(\tau) \leqslant f(n) + n^{0.501} (if nn is large enough). Denote by C(τ)C(\tau) the set of elements x∈[n]x \in [n] for which τk(x)=τ(…τ⏟k(x)… )=x\tau^k(x) = \underbrace{\tau(\dots\tau}_{k}(x)\dots) = x for some k>0k > 0. It is immediate that C(τ)C(\tau) is a τ\tau-invariant set; let τc=τ∣C(τ)\tau_c = \tau|_{C(\tau)}, that is a permutation on C(τ)C(\tau).

Let NN be the order of this permutation τc\tau_c, clearly N⩽g(n)N \leqslant g(n). Consider an arbitrary element x∈[n]∖C(τ)x \in [n] \setminus C(\tau). The sequence x,τ(x),τ2(x),…x, \tau(x), \tau^2(x), \dots is eventually periodic, but not from the beginning, because x∉C(τ)x \notin C(\tau).

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

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

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

Transcribed from the official solutions, page 6. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?