IMC 2025, Ημέρα 1, Θέμα 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 .
Πρωτότυπο από το επίσημο 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)
Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.
Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.
Επίσημη λύση
(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 .
Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδα 6. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.
Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.
Πώς πήγε;
Οι κινήσεις που σημειώνεις επιστρέφουν νωρίτερα στη διαλογή.