IMC 2023, Ημέρα 1, Θέμα 5
Fix positive integers and such that and a set consisting of fruits. A permutation is a sequence such that . Ivan prefers some (at least one) of these permutations. He realized that for every preferred permutation , there exist indices with the following property: for every , if he swaps and , he obtains another preferred permutation.
Prove that he prefers at least permutations.
Πρωτότυπο από το επίσημο PDF

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.
Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.
Επίσημη λύση
(proposed by Ivan Mitrofanov, École Normale Superieur Paris)
Hint: For every permutation of , choose a preferred permutation such that is maximal.
Solution. Let be the set of all permutations of , and let be the set of preferred permutations. For every permutation and , let denote the unique number with .
For every , define
For every permutation , we can choose a permutation for which is maximal, and then we have ; hence, all is contained in at least one set .
So, it suffices to prove that for every preferred permutation . Fix , and consider an arbitrary . Let the indices be as in the statement of the problem, and let for .
For consider the permutation obtained from by swapping and . Since , the definition of provides
Therefore, the elements appear in in this order. There are exactly permutations with this property, so .
Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδα 5. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.
Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.
Πώς πήγε;
Οι κινήσεις που σημειώνεις επιστρέφουν νωρίτερα στη διαλογή.