Maximizing score of permutations

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Maximizing score of permutations

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Malaysian IMO TST 2023 P2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

474 posts

#1 h Apr 29, 2023, 9:14 AM

Y by

Let $a_1, a_2, \cdots, a_n$ be a sequence of real numbers with $a_1+a_2+\cdots+a_n=0$ . Define the score $S(\sigma)$ of a permutation $\sigma=(b_1, \cdots b_n)$ of $(a_1, \cdots a_n)$ to be the minima of the sum $(x_1-b_1)^2+\cdots+(x_n-b_n)^2$ over all real numbers $x_1\le \cdots \le x_n$ .

Prove that $S(\sigma)$ attains the maxima over all permutations $\sigma$ , if and only if for all $1\le k\le n$ , $b_1+b_2+\cdots+b_k\ge 0.$
Proposed by Anzo Teh Zhao Yang

This post has been edited 3 times. Last edited by navi_09220114, Apr 21, 2024, 6:59 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

124 posts

#2 h Apr 29, 2023, 12:00 PM

Y by

Proposer's note: this is inspired by the property of isotonic regression (monotone smoothing), cf. https://link.springer.com/article/10.1007/BF01580873.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1069 posts

gghx

#3 h May 5, 2023, 5:49 AM

Y by

There exists $y_1$ and $y_2,\cdots y_n\ge 0$ such that $x_k=\sum\limits_{i=1}^k y_i$ . Let $\sum b_i^2=\sum a_i^2=T$ .
The expression becomes $\sum (x_i-b_i)^2=\sum b_i^2+\sum x_i^2-2\sum x_ib_i=T+\sum x_i^2-2\sum(y_1+\cdots+y_i)b_i$ .
This is equal to $T+\sum x_i^2-2\sum (b_i+\cdots+b_n)y_i=T+\sum x_i^2+2\sum (b_1+\cdots+b_{i-1})y_i$ . (note $y_1$ is not in the last sum).
Since all $y_{\ge 2}$ are non-negative, if $b_1+\cdots+b_{i-1}\ge 0$ then the sum is at least $T$ , attainable when all $y_i=0$ . This shows one direction.

Suppose $b_1+\cdots+b_k<0$ . Let it be $-c$ for $c>0$ . We take all $y_i=0$ except $y_{k+1}=Y$ .
This gives $T+(n-k)Y^2-2cY$ . Taking $Y$ sufficiently small (and positive) we can make it $<T$ , finishing the proof.

This post has been edited 2 times. Last edited by gghx, May 6, 2023, 12:25 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

474 posts

#4 h Oct 13, 2023, 7:00 AM

Y by

Official Solution:

Solution: Here we show that the two conditions are equivalent. Observe that by looking at $x_1=\cdots = x_n=0$ we have $S(\sigma) \le \sum a_i^2$ for all permutations $\sigma$ .

Suppose $b_1+\cdots + b_k < 0$ for some $k$ , then choosing $y_1=\cdots = y_k=-1$ and $y_{k+1}+\cdots + y_n=0$ yields $b_1y_1+\cdots + b_ny_n = -(y_1+\cdots + y_k)>0$ . In addition, we may choose

https://cdn.aops.com/images/5/c/e/5ce98bf6016734c348abd097d06cb896599a9180.png

This gives $S(\sigma)\le \sum a_n^2 - \frac{(b_1+\cdots + b_k)^2}{k} < \sum a_i^2$ .

On the other hand, suppose that $b_1 + \cdots + b_k\ge 0$ for all $k\ge 1$ . Notice that such permutation exists:
for example, take $\sigma$ such that $b_1\ge \cdots \ge b_n$ . We will show that $b_1y_1 + \cdots + b_ny_n\le 0$ for all $y_1\le \cdots \le y_n$ .
Since $\sum b_i=0$ , replacing $(y_1, \cdots, y_n)$ with $(y_1 - c, \cdots, y_n-c)$ for any $c$ will still yield the same sum
$\sum b_iy_i$ . We now choose $c=y_n$ ; all the $y_i$ 's are now nonpositive. Iteratively, let $k$ be the largest index with $y_k < 0$ , while $y_{k+1}=\cdots = y_n=0$ . We replace $y_1, \cdots, y_k$ with $y_1-y_k, \cdots, y_k-y_k$ , the cross term $\sum_{i=1}^n b_iy_i$ is now increased by $-y_k\sum_{i=1}^k b_i \ge 0$ . The new sequence $y_1', \cdots, y_k', y_{k+1}, \cdots, y_n$ is still nondecreasing.

We now end up with $y_1=\cdots=y_n=0$ . Since the sum $\sum b_iy_i$ never decreases throughout the iteration, it follows that it has to be nonpositive to start with.

Finally, what we established implies the other condition: for all $x_1\le \cdots \le x_n$ we then have $\sum (x_i-b_i)^2=\sum a_i^2 + x_i^2 - 2b_ix_i\ge \sum a_i^2 - 2\sum b_ix_i\ge \sum a_i^2$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

52 posts

#5 h Mar 23, 2025, 10:40 PM

Y by

Note that:
$\sum (x_i - b_i)^2 = \sum b_i^2 + \sum x_i^2 - 2 \sum x_ib_i$ Where if we call $S_i = b_1 + \cdots + b_i$ (being $S_0 = 0$ ) we have:
$\sum_{i=1}^n x_ib_i = \sum x_i (S_i - S_{i-1}) = \sum_{i=1}^{n-1} S_i(x_i - x_{i+1}) + x_n (b_1 + \cdots + b_n) = \sum_{i=1}^{n-1} S_i(x_i - x_{i+1})$ So:
$\sum (x_i - b_i)^2 = \sum a_i^2 + \sum x_i^2 + 2 \sum_{i=1}^{n-1} S_i(x_{i+1} - x_i)$ If $\sigma$ is such that every $S_i \ge 0$ is clear that, because every $x_{i+1} - x_i \geq 0$ , that expression is greater or equal to $\sum a_i^2$ . Achieving that minimum if every $x_i = 0$ .
If $\sigma$ is such that there exists some $S_k < 0$ take $x_1 = \cdots = x_k = 0$ and $x_{k+1} = \cdots = x_n = c > 0$ with $c$ being small, now this expression is:
$\sum a_i^2 + c^2 (n-k) + cS_k = \sum a_i^2 + c ( c(n-k) + S_k) < \sum a_i^2$ By choosing some tiny $c$ .
The result follows by looking at these two last observations.

This post has been edited 1 time. Last edited by Manteca, Mar 23, 2025, 10:41 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a