International Mathematics Competition
for University Students
2023

IMC2023: Day 1, Problem 5

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

Prove that he prefers at least \(\displaystyle k!\) permutations.

Ivan Mitrofanov, École Normale Superieur Paris

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

For every \(\displaystyle x\in P\), define

\(\displaystyle A(x) = \bigg\{ z\in S~:~ \forall y\in P~~\sum_{m\in M} x^{-1}(m)z^{-1}(m)\geq \sum_{m\in M} y^{-1}(m)z^{-1}(m) \bigg\}. \)

For every permutation \(\displaystyle z\in S\), we can choose a permutation \(\displaystyle x\in P\) for which \(\displaystyle \sum\limits_{m\in M} x^{-1}(m)z^{-1}(m)\) is maximal, and then we have \(\displaystyle z\in A(x)\); hence, all \(\displaystyle z\in S\) is contained in at least one set \(\displaystyle A(x)\); the sets \(\displaystyle A(x)\) cover \(\displaystyle S\).

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

For \(\displaystyle s=1,2,\ldots,k-1\) consider the permutation \(\displaystyle y\) obtained from \(\displaystyle x\) by switching \(\displaystyle m_s\) and \(\displaystyle m_{s+1}\). Since \(\displaystyle y\in P\), the definition of \(\displaystyle A(x)\) provides

\(\displaystyle i_s z^{-1}(m_s)+i_{s+1} z^{-1}(m_{s+1}) \geq i_{s+1} z^{-1}(m_s)+i_{s} z^{-1}(m_{s+1}), \)

\(\displaystyle z^{-1}(m_{s+1})\geq z^{-1}(m_s).\)

Therefore, the elements \(\displaystyle m_1,m_2,\ldots,m_k\) appear in \(\displaystyle z\) in this order. There are exactly \(\displaystyle n!/k!\) permutations with this property, so \(\displaystyle \big|A(x)\big|\le\dfrac{n!}{k!}\).