uniolympiads Ελληνικά

IMC 2023, Day 1, Problem 5

Fix positive integers nn and kk such that 2≤k≤n2 \le k \le n and a set MM consisting of nn fruits. A permutation is a sequence x=(x1,x2,…,xn)x = (x_1, x_2, \dots, x_n) such that {x1,…,xn}=M\{x_1, \dots, x_n\} = M. Ivan prefers some (at least one) of these permutations. He realized that for every preferred permutation xx, there exist kk indices i1<i2<⋯<iki_1 < i_2 < \dots < i_k with the following property: for every 1≤j<k1 \le j < k, if he swaps xijx_{i_j} and xij+1x_{i_{j+1}}, he obtains another preferred permutation.

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

Original from the official PDFFix positive integers n and k such that 2 ≤ k ≤ n and a set M consisting of n fruits. A permutation is a sequence x = (x 1 , x 2 , . . . , x n ) such that {x 1 , . . . , 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 < . . . < i k with the following property: for every 1 ≤ 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.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(proposed by Ivan Mitrofanov, École Normale Superieur Paris)

Hint: For every permutation zz of MM, choose a preferred permutation xx such that ∑m∈Mx−1(m)z−1(m)\sum\limits_{m\in M} x^{-1}(m)z^{-1}(m) is maximal.

Solution. Let SS be the set of all n!n! permutations of MM, and let PP be the set of preferred permutations. For every permutation x∈Sx \in S and m∈Mm \in M, let x−1(m)x^{-1}(m) denote the unique number i∈{1,2,…,n}i \in \{1,2,\dots,n\} with xi=mx_i = m.

For every x∈Px \in P, define

A(x)={z∈S : ∀y∈P∑m∈Mx−1(m)z−1(m)≥∑m∈My−1(m)z−1(m)}.A(x) = \left\{ z \in S \ : \ \forall y \in P \quad \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∈Sz \in S, we can choose a permutation x∈Px \in P for which ∑m∈Mx−1(m)z−1(m)\sum\limits_{m\in M} x^{-1}(m)z^{-1}(m) is maximal, and then we have z∈A(x)z \in A(x); hence, all z∈Sz \in S is contained in at least one set A(x)A(x).

So, it suffices to prove that ∣A(x)∣≤n!k!\bigl|A(x)\bigr| \le \dfrac{n!}{k!} for every preferred permutation xx. Fix x∈Px \in P, and consider an arbitrary z∈A(x)z \in A(x). Let the indices i1<…<iki_1 < \ldots < i_k be as in the statement of the problem, and let mj=xijm_j = x_{i_j} for j=1,2,…,kj = 1,2,\dots,k.

For s=1,2,…,k−1s = 1,2,\dots,k-1 consider the permutation yy obtained from xx by swapping msm_s and ms+1m_{s+1}. Since y∈Py \in P, the definition of A(x)A(x) provides

isz−1(ms)+is+1z−1(ms+1)≥is+1z−1(ms)+isz−1(ms+1),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(ms+1)≥z−1(ms).z^{-1}(m_{s+1}) \ge z^{-1}(m_s).

Therefore, the elements m1,m2,…,mkm_1, m_2, \dots, m_k appear in zz in this order. There are exactly n!/k!n!/k! permutations with this property, so ∣A(x)∣≤n!k!\bigl|A(x)\bigr| \le \dfrac{n!}{k!}.

Transcribed from the official solutions, page 5. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?