Berkeley Math Circle Monthly Contest #1

Solution:
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 i<j \leq 2000}(j-i)$ minus the sum of $j-i$ over pairs for which $a_{i}=a_{j}$. So our goal is equivalent to minimizing the latter sum. Fix a positive integer $k$, and suppose there are $k$ values of $i$ with $a_{i}=0$ (and $2000-k$ values with $a_{i}=1$). If we consider the sum of $j-i$ over all pairs $i<j$ with $a_{i}=a_{j}=0$, this sum is clearly minimized when all the $i$'s with $a_{i}=0$ are consecutive; likewise the sum over all pairs with $a_{i}=a_{j}=1$ is minimized when all the $1$'s are consecutive. So we may restrict our attention to the case where $a_{1}=a_{2}=\cdots=a_{k}=0$ and $a_{k+1}=\cdots=a_{2000}=1$. (The case where the block of $1$'s precedes the block of $0$'s is symmetrically equivalent.)

In this case, the sum $S$ comes out to be
$$\begin{aligned} & \sum_{\substack{1 \leq i<j \leq 2000 \\\ a_{i} \neq a_{j}}}(j-i)=\sum_{i=1}^{k} \sum_{j=k+1}^{2000}(j-i)=\sum_{j=k+1}^{2000}\left(\sum_{i=1}^{k} j\right)-\sum_{i=1}^{k}\left(\sum_{j=k+1}^{2000} i\right)=\sum_{j=k+1}^{2000} k j-\sum_{i=1}^{k}(2000-k) i \\ = & \frac{(2000-k)(2000+[k+1])}{2}-(2000-k) \frac{k(k+1)}{2}=1000 k(2000-k)=1000\left(1000^{2}-[k-1000]^{2}\right) \end{aligned}$$
which is at most $1000^{3}$, with equality holding iff $k=1000$. So $1000^{3}$ is our desired maximum, attained when $a_{i}=0$ for $i \leq 1000$ and $a_{i}=1$ for $i>1000$.