IMC 2023, Day 1, Problem 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.
Original from the official PDF

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 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 .
Transcribed from the official solutions, page 5. 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.