Find the maximum of the $S=|a_1-b_1|+|a_2-b_2|+\cdots+|a_{31}-b_{31}|$

Solution 1:

This is an outline of my solution.

Suppose $a_1<a_2<a_3<\dots<a_{31},b_1<b_2<b_3<\dots<b_{31}$ satisfies all conditions and maximises the expression.

We sort the ordered pairs $(a_i,b_i)$ in non-decreasing $a_i-b_i$. Let the sorted sequence be relabelled $(a_{\sigma(i)},b_{\sigma(i)})$

Then we generate another sequence $c_1<c_2<c_3<\dots<c_{31},d_1<d_2<d_3<\dots<d_{31}$, such that $c_i-d_i=a_{\sigma(i)}-b_{\sigma(i)}$, and this new sequence satisfies all conditions. To generate this sequence, we impose the extra condition that $d$ is an arithmetic progression with common difference $1$.

Clearly, the value of the expression has not changed.

Let's manipulate the expressions now.

$$\sum_{a_i>b_i}(a_i-b_i)=\sum_{a_i>b_i}(a_i-b_i)-\sum a_i+\sum b_i=\sum_{a_i\leq b_i}(b_i-a_i)$$

The original sum is now:

$$S=\sum_{a_i>b_i}(a_i-b_i)+\sum_{a_i\leq b_i}(b_i-a_i)=\sum_{c_i>d_i}(c_i-d_i)+\sum_{c_i\leq d_i}(d_i-c_i)$$

Since both sums are the same, we can take $(2-\lambda)$ of the first sum and $\lambda$ of the second sum and the sum will still be the same. Let $k$ be the number of terms in the second sum. $c_i$ has the nice property such that $c_1$ to $c_k$ are in the second sum. Here, choose $\lambda=\frac{2(31-k)}{31}$. The motivation for this is that we want to take them in a way such that terms cancel nicely later, so we take the sums in the ratio $k:31-k$.

$$S=\frac{2k}{31}\sum_{k<i\leq31}(c_i-d_i)+\frac{2(31-k)}{31}\sum_{i\leq k}(d_i-c_i)$$

Let's combine the $2$ sums.

$$S=\frac{2}{31}\left(k\sum_{k<i\leq31}(c_i-d_i)+(31-k)\sum_{i\leq k}(d_i-c_i)\right)$$

Magic double summation time!

$$S=\frac{2}{31}\left(\sum_{k<i\leq31}\sum_{j\leq k}((d_j-c_j)+(c_i-d_i))\right)$$

Let's use the properties of $c_i$ and $d_i$. We know $c_i\leq2015-31+i$ and $c_j\geq j$. Also, we know $d_j-d_i=j-i$.

$$S\leq\frac{2}{31}\left(\sum_{k<i\leq31}\sum_{j\leq k}(j-i+2015-31+i-j)\right)$$

$$S\leq\frac{2}{31}\left(\sum_{k<i\leq31}\sum_{j\leq k}1984\right)$$

Now the summation is just multiplication.

$$S\leq\frac{2}{31}(31-k)k\times1984$$

This quadratic is maximised when $k=15$ or $k=16$.

$$S\leq30720$$

With the construction, we are done.