MathDB
Maximizing score of permutations

Source: Malaysian IMO TST 2023 P2

April 29, 2023
algebra

Problem Statement

Let a1,a2,⋯ ,ana_1, a_2, \cdots, a_n be a sequence of real numbers with a1+a2+⋯+an=0a_1+a_2+\cdots+a_n=0. Define the score S(σ)S(\sigma) of a permutation σ=(b1,⋯bn)\sigma=(b_1, \cdots b_n) of (a1,⋯an)(a_1, \cdots a_n) to be the minima of the sum (x1−b1)2+⋯+(xn−bn)2(x_1-b_1)^2+\cdots+(x_n-b_n)^2 over all real numbers x1≤⋯≤xnx_1\le \cdots \le x_n.
Prove that S(σ)S(\sigma) attains the maxima over all permutations σ\sigma, if and only if for all 1≤k≤n1\le k\le n, b1+b2+⋯+bk≥0.b_1+b_2+\cdots+b_k\ge 0.
Proposed by Anzo Teh Zhao Yang
Back to ProblemsView on AoPS