IMC 2023 · Problem 5

Fix positive integers $n$ and $k$ such that $2 \le k \le n$ and a set $M$ consisting of $n$ fruits. A permutation is a sequence $x = (x_1, x_2, \ldots, x_n)$ such that $\{x_1, \ldots, x_n\} = M$. Ivan prefers some (at least one) of these permutations. He realized that for every preferred permutation $x$, there exist $k$ indices $i_1 < i_2 < \ldots < i_k$ with the following property: for every $1 \le j < k$, if he swaps $x_{i_j}$ and $x_{i_{j+1}}$, he obtains another preferred permutation.

Prove that he prefers at least $k!$ permutations.