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

Hint: For every permutation \(\displaystyle z\) of \(\displaystyle M\), take a preferred permutation \(\displaystyle x\) such that \(\displaystyle \sum\limits_{m\in M} x^{-1}(m)z^{-1}(m)\) is maximal.

  Solution