IMC 2023 · Day 1 · P5

Hint: For every permutation $z$ of $M$, choose a preferred permutation $x$ such that $\sum_{m \in M} x^{-1}(m) z^{-1}(m)$ is maximal.

Let $S$ be the set of all $n!$ permutations of $M$, and let $P$ be the set of preferred permutations. For every permutation $x \in S$ and $m \in M$, let $x^{-1}(m)$ denote the unique number $i \in \{1, 2, \dots, n\}$ with $x_i = m$.

For every $x \in P$, define $$A(x) = \left\{ z \in S : \forall y \in P \ \sum_{m \in M} x^{-1}(m) z^{-1}(m) \ge \sum_{m \in M} y^{-1}(m) z^{-1}(m) \right\}.$$ For every permutation $z \in S$, we can choose a permutation $x \in P$ for which $\sum_{m \in M} x^{-1}(m) z^{-1}(m)$ is maximal, and then we have $z \in A(x)$; hence, all $z \in S$ is contained in at least one set $A(x)$.

So, it suffices to prove that $\bigl| A(x) \bigr| \le \dfrac{n!}{k!}$ for every preferred permutation $x$. Fix $x \in P$, and consider an arbitrary $z \in A(x)$. Let the indices $i_1 < \dots < i_k$ be as in the statement of the problem, and let $m_j = x_{i_j}$ for $j = 1, 2, \dots, k$.

For $s = 1, 2, \dots, k-1$ consider the permutation $y$ obtained from $x$ by swapping $m_s$ and $m_{s+1}$. Since $y \in P$, the definition of $A(x)$ provides $$\begin{gather*} i_s z^{-1}(m_s) + i_{s+1} z^{-1}(m_{s+1}) \ge i_{s+1} z^{-1}(m_s) + i_s z^{-1}(m_{s+1}), \\ z^{-1}(m_{s+1}) \ge z^{-1}(m_s). \end{gather*}$$ Therefore, the elements $m_1, m_2, \dots, m_k$ appear in $z$ in this order. There are exactly $n!/k!$ permutations with this property, so $\bigl| A(x) \bigr| \le \dfrac{n!}{k!}$.