Let $a_{1}, a_{2}, \ldots, a_{2000}$ be real numbers in the interval $[0,1]$. Find the maximum possible value of

$$
\sum_{1 \leq i<j \leq 2000}(j-i)\left|a_{j}-a_{i}\right|
$$
The answer is $1,000,000,000$. First, note that the desired sum $S$ is convex as a function of each $a_{i}$. (Indeed, $\left|a_{i}-a\right|$ is convex for any real number $a$, and a sum of convex functions is itself convex.) Consequently, it attains a maximum at some point where each variable lies at an endpoint of its interval, i.e. $S$ has a maximum with each $a_{i}$ equal to either 0 or 1 . So we may restrict our attention to these cases.

Then $\left|a_{j}-a_{i}\right|=0$ if $a_{i}=a_{j}$ and 1 otherwise, so $S$ is really the sum of all values of $j-i$ where $a_{i} \neq a_{j}$. Equivalently, it equals $\sum_{1 \leq i1000$.

Of course, essentially the same proof shows that, if 2000 is replaced by any positive integer $n$, the maximum of $S$ is $n^{3} / 8$ when $n$ is even and $\left(n^{3}-n\right) / 8$ when $n$ is odd.

Solutions (C) 2000, Berkeley Math Circle.