Maximise $\left( \sum_{i=1}^{n} p_i \cdot i \right) - \left( \max_{j=1}^{n} p_j \cdot j \right)$ with $p$ permutation of size $n$

Question

I'm trying to maximise the following value:

$\left( \sum_{i=1}^{n} p_i \cdot i \right) - \left( \max_{j=1}^{n} p_j \cdot j \right)$

where $p$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order (a permutation of $\{1, 2, \dots, n\}$). I have to find an optimal permutation $p$.

---

A brute force approach in Python can allow us detect a pattern:

from __future__ import annotations  # noqa
from itertools import permutations  # noqa

if __name__ == "__main__":
    for n in range(1, 12):
        elements = range(1, n+1)
        perms = permutations(elements, n)
        best: int = 0
        best_perm: list[int] | None = None
        for perm in perms:
            perm: list[int] = list(perm)
            s = 0
            max = 0
            for i in range(0, n):
                s += (i+1) * perm[i]
                if (i+1) * perm[i] > max:
                    max = (i+1) * perm[i]
            s -= max
            if s >= best:
                best = s
                best_perm = perm
        print(f"{n=}, {best_perm=}, {best=}")

Outputs:

n=1, best_perm=[1], best=0
n=2, best_perm=[2, 1], best=2
n=3, best_perm=[1, 3, 2], best=7
n=4, best_perm=[1, 4, 3, 2], best=17
n=5, best_perm=[1, 2, 5, 4, 3], best=35
n=6, best_perm=[1, 2, 3, 6, 5, 4], best=62
n=7, best_perm=[1, 2, 3, 7, 6, 5, 4], best=100
n=8, best_perm=[1, 2, 3, 4, 8, 7, 6, 5], best=152
n=9, best_perm=[1, 2, 3, 4, 5, 9, 8, 7, 6], best=219
n=10, best_perm=[1, 2, 3, 4, 5, 6, 10, 9, 8, 7], best=303
n=11, best_perm=[1, 2, 3, 4, 5, 6, 7, 11, 10, 9, 8], best=406

We can notice that the numbers in the permutation "go up", then "go down starting from $n$". It makes sense (small numbers in the beginning, and we can't put the largest number at the end since there is the $\max_{j=1}^{n} p_j \cdot j$ term subtracted in the function we are trying to maximise). Could it potentially fail for large values of $n$? However, I have thoroughly tested all computationally-feasible cases and have not discovered a counterexample.

I'm struggling to find a proof. This post is adapted from the Problem - C competition from codeforces that ended on the 12th of August 2023.

EDIT: I'm looking for a proof of the pattern, but there might be a proof to find an permutation that maximises the value we are trying to maximise, which would be even more satisfying.

Answer 1

This is not a full proof but I hope it provides some insight

If we assume the optimal solution is in form of

$p_i = \begin{cases} i & \text{if }~~i=1,2,...,m\\ n+m+1-i & \text{if}~~i=m+1,...,n \end{cases}$

for $i>m$, it we can show that $a_i = ip_i$ has maximum at $i=\lceil \frac{m+n}{2} \rceil$. This can be shown considering the fact that $a_i = ip_i$ is a concave function of $i$ and

$i^* = \min_{i>m} {a_{i+1}\le a_{i}}$.

$a_{i+1}\le a_i \Rightarrow (i+1)(n+m-i)\le i(n+m+1-i) \Rightarrow i\ge \frac{n+m}{2} \Rightarrow i^* = \lceil \frac{n+m}{2} \rceil$.

Also it is clear that $a_i>a_j$ if $i>m$ and $j\le m$. Therefore, $\max_{i \in \{1,2,..,n\}}{a_i} =\lceil \frac{n+m}{2} \rceil (n+m+1-\lceil \frac{n+m}{2} \rceil) =\begin{cases} (\frac{n+m}{2})(\frac{n+m}{2}+1) & \text{if }~~n+m~~\text{even}\\ (\frac{n+m+1}{2})^2 & \text{if}~~~~n+m~~\text{odd} \end{cases}$

Now, we try to find the the value of $m$ that maximizes our objective function

$f(m)=\sum_{i=1}^m i^2 + \sum_{i=m+1}^n a_i - a_{\lceil \frac{n+m}{2} \rceil}$. We further simplify as $f(m)=\sum_{i=1}^m i^2 - \sum_{i=m+1}^n i^2+ (n+m+1)\sum_{i=m+1}^n i - a_{\lceil \frac{n+m}{2} \rceil} = 2\sum_{i=1}^m i^2 - \sum_{i=1}^n i^2+ (n+m+1)\sum_{i=m+1}^n i - a_{\lceil \frac{n+m}{2} \rceil}$ $=\frac{m(m+1)(2m+1)}{3}-\frac{n(n+1)(2n+1)}{6}+\frac{(n+m+1)^2(n-m)}{2}-a_{\lceil \frac{n+m}{2} \rceil}$. It is easy to show that this function is also concave as

$\frac{\partial^2 f}{\partial m^2} = (4m+2)-(n+3m+2)-\frac{1}{2}=-(n-m+\frac{1}{2})<0$. So,

$m^* = min_m {f(m+1)\le f(m)}$.

$f(m+1)\le f(m) \Rightarrow 2\sum_{i=1}^{m+1} i^2 - \sum_{i=1}^n i^2+ (n+m+2)\sum_{i=m+2}^n i - a_{\lceil \frac{n+m+1}{2} \rceil} \le 2\sum_{i=1}^m i^2 - \sum_{i=1}^n i^2+ (n+m+1)\sum_{i=m+1}^n i - a_{\lceil \frac{n+m}{2} \rceil}$

$\Rightarrow 2(m+1)^2 - (n+m+1)(m+1) + \sum_{i=m+2}^n i + a_{\lceil \frac{n+m}{2} \rceil}-a_{\lceil \frac{n+m+1}{2} \rceil}\le 0$

$\Rightarrow -(n-m-1)(m+1) + \frac{(n+m+2)(n-m-1)}{2} - \lceil \frac{n+m+1}{2} \rceil\le 0$

$\text{if }~~n+m~~\text{even} \Rightarrow {(n-m)^2 -n+m} - 2 -n -m \le 0 \Rightarrow (n-m)^2 \le 2n+2) \rightarrow m\ge n-\sqrt{2n+2}$

$\text{if }~~n+m~~\text{odd} \Rightarrow {(n-m)^2 -n+m} - 1 -n -m \le 0 \Rightarrow (n-m)^2 \le 2n+1 \rightarrow m\ge n-\sqrt{2n+1}$

It can be shown that $m^* = n- \lfloor \sqrt{2n+1}\rfloor$ is the solution for any case. Hence, the optimal solution of proposed form is:

$p_i = \begin{cases} i & \text{if }~~i=1,2,...,n- \lfloor \sqrt{2n+1}\rfloor\\ 2n- \lfloor \sqrt{2n+1}\rfloor+1-i & \text{if}~~i=n- \lfloor \sqrt{2n+1}\rfloor+1,...,n \end{cases}$

Answer 2

This solution is slightly handwave-y and complements the solution by Mehdi by attempting to show that the conjectured structure of the maximizing permutation $p$ is correct. I may return later to make it more rigorous.

For a permutation $p\in S_n$, denote $f(p)=\left(\sum_{i=1}^{n}ip_i\right)-\left(\max_{1\le i\le n}ip_i\right)$.

Suppose that $\max_{1\le i\le n} ip_i = i_0p_{i_0}$ for some $i_0\in[n]=\{1,\dots,n\}$. This means that $ip_i\le i_0p_{i_0}$ for all $i\in[n]$. In particular, this implies that $$ \begin{split} p(i)<p_{i_0} \qquad &\text{if} \qquad i\in[i_0+1,n],\\ i<i_0 \qquad &\text{if} \qquad p_i\in[p_{i_0}+1,n], \end{split} $$

===begin handwave 1===

Therefore, to maximize $f(p)$ while keeping the $\max_{1\le i\le n}ip_i$ at the same position $i_0$ and value $p_{i_0}$, we should aim to place the values $p_i$ greater than $p_{i_0}$ as far to the right as possible (given the constraints), i.e. place the interval $H$ of those values immediately to the left of $p_{i_0}$, and then partition the values less than $p_{i_0}$ into two intervals, $M$ and $L$, so that all values in $M$ are greater than all values in $L$, all values in $M$ are to the right of $p_{i_0}$, and all values in $L$ are to the left of $H$. We may denote this by $$ p=L\oplus(H\ominus \{p_{i_0}\}\ominus M), $$ where $\oplus$ and $\ominus$ denote the direct sum and the skew-sum of intervals, respectively.

===end handwave 1===

We know that $|H|=n-p_{i_0}$ and $|M|=n-i_0$, so $$|H\ominus\{p_{i_0}\}\ominus M|=(n-p_{i_0})+1+(n-i_0)=2n+1-(i_0+p_{i_0}),$$ and thus $|L|=n-|H\ominus\{p_{i_0}\}\ominus M|=(i_0+p_{i_0})-n-1$.

Now we want to show that $|p_{i_0}-i_0|\le 1$. Suppose this is false, then either $i_0<p_{i_0}-1$ or $p_{i_0}<i_0-1$.

If $i_0<p_{i_0}-1$, then $i_0<n$, so $p_{i_0}-1$ should be placed to the right of $p_{i_0}$, say, in position $i_1>i_0$. Then $i_1(p_{i_0}-1)\le i_0p_{i_0}$, so $$ 0<i_1-i_0\le\frac{i_0p_{i_0}}{p_{i_0}-1}-i_0=\frac{i_0}{p_{i_0}-1}<1, $$ which is impossible.

Similarly, if $p_{i_0}<i_0-1$, then $p_{i_0}<n$, so $p_{i_0-1}>p_{i_0}$. We know that $(i_0-1)p_{i_0-1}\le i_0p_{i_0}$, so $$ 0<p_{i_0-1}-p_{i_0}\le\frac{i_0p_{i_0}}{i_0-1}-p_{i_0}=\frac{p_{i_0}}{i_0-1}<1, $$ which is impossible.

Thus, $|p_{i_0}-i_0|\le 1$. This splits into two cases: either $p_{i_0}=i_0$, or $p_{i_0}=i_0\pm 1$. In the second case, by the same argument as above, we should also have $p_{i_0\pm 1}=i_0$, where the signs ($+$ or $-$) must agree.

Thus, we can modify the notation for the parts of $p$ slightly. In the two-line notation, we have $$ p= \begin{pmatrix} L & M & C & H\\ L & H & C & M \end{pmatrix}, $$ where $L<M<C<H$ (i.e. every value in $L$ is less than every value in $M$, etc.), $|H|=|M|$, and $$ C= \begin{pmatrix} i_0\\ i_0 \end{pmatrix} \qquad \text{or} \qquad C= \begin{pmatrix} i_0-1 & i_0\\ i_0 & i_0-1 \end{pmatrix}. $$ Also, since the $p$ maps the interval $L$ to itself, the maximizing permutation should have the entries of $L$ in increasing order, i.e. $p$ begins with $(1,2,\dots,|L|)$.

Finally, we show that the values in the intervals $H$ and $M$ should be in decreasing order (while their positions are in increasing order, of course) close enough to the maximizing value of $i_0$.

===begin handwave 2===

Once this is shown, we should show that if $i_0$ is far enough away from the maximizing value (i.e., too small), then it can be increased in a way that yields a permutation $p$ with a higher $f(p)$.

===end handwave 2===

We will only work out the case when $p_{i_0}=i_0$, since the other case is similar, with resulting values that are almost the same. We will also only show that $M$ must be in decreasing order, as the argument for the values in $H$ is very similar. Suppose that the values of $M$ are not in decreasing order in the positions in $H$. Then there exists some $j>0$ such that $p_{i_0+1+j}\ge i_0-j$. Recall that $$ i_0^2=i_0p_{i_0}>(i_0+1+j)p_{i_0+1+j}\ge (i_0+1+j)(i_0-j)=i_0^2-j^2-j+i_0, $$ so $$ j^2+j-i_0>0 $$ for some value $j\in[n-i_0-1]$. Thus, to prevent that from happening for any $j\in[n-i_0-1]$, we need to choose $i_0$ so that $$ (n-i_0-1)^2+(n-i_0-1)-i_0<0, $$ i.e. $$ i_0^2-2ni_0+n^2-n<0. $$ This implies that $i_0\in[n-\sqrt{n},n+\sqrt{n}]$, but since, obviously, $i_0\le n$ and $i_0\in\mathbb{N}$, we simply have $$ i_0\ge n-\left\lfloor\sqrt{n}\right\rfloor. $$ Thus, the values in both $H$ and $M$ must be in decreasing order if $i_0\ge n-\left\lfloor\sqrt{n}\right\rfloor$, which makes the length of the decreasing segment $\le 2\left\lfloor\sqrt{n}\right\rfloor+2$, and this bound is well above $\left\lfloor\sqrt{2n+1}\right\rfloor$.

That, more or less, ends this (sketch of a) proof.