IMC 2025, Day 1, Problem 5
For a positive integer , let . Denote by the set of all bijections from to , and let be the set of all maps from to . Define the order of a map as the number of distinct maps in the set where denotes composition. Finally, let
Prove that for sufficiently large .
Original from the official PDF
![For 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.](/archive/imc/imc-2025-d1-p5.png)
This transcription was compared symbol by symbol with the original, but not yet by a person.
Work for at least 45 minutes before opening the solution.
Official solution
(proposed by Fedor Petrov, St Petersburg State University)
Solution. For every we need to prove that (if is large enough). Denote by the set of elements for which for some . It is immediate that is a -invariant set; let , that is a permutation on .
Let be the order of this permutation , clearly . Consider an arbitrary element . The sequence is eventually periodic, but not from the beginning, because .
Let be the minimal number for which is in the period; equivalently, this is the minimal number for which . Let . Note that for all , since for all . Therefore, . Thus, if , we are done.
Now assume that , that is, for some . It yields . Consider the cycle lengths of the permutation . We claim that there exists a prime number which does not divide any of these lengths. Indeed, otherwise the sum of cycle lengths of is not less than the sum of all prime numbers not exceeding (because each positive integer is not less than the sum of its prime divisors, that in turn follows from for ). But for large , the number of prime numbers less than is at least by some weak version of Prime Number Theorem (that also has many short proofs). Therefore, their sum exceeds , contradiction.
Now we may consider the permutation which acts as on and has a cycle of length on . The order of is not less than , therefore , and by the above argument we get for large .
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?
Moves you mark come back sooner in triage.