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.