NMO Selection Tests for BMO and IMO

The required minimum is $n-1$ and is achieved, for instance, by $a_1 < a_2 = \dots = a_n$. The maximum is $\lfloor \frac{1}{2}n \rfloor \lfloor \frac{1}{2}(n+1) \rfloor$ and is achieved, for instance, by
$$a_1 = \dots = a_{\lfloor n/2 \rfloor} < a_{\lfloor n/2 \rfloor+1} = \dots = a_n.$$
In each case, verification is routine and is hence omitted.

We now show that $(n-1)d \le s \le \lfloor \frac{1}{2}n \rfloor \lfloor \frac{1}{2}(n+1) \rfloor d$. Clearly, we may and will assume $a_1 \le a_2 \le \dots \le a_n$, so $s = \sum_{1 \le i < j \le n} (a_j - a_i)$. Let $d_k = a_{k+1} - a_k$, $k = 1, \dots, n-1$, so $d = d_1 + \dots + d_{n-1}$.

Express every $a_j - a_i$, $1 \le i < j \le n$, and hence $s$, in terms of the $d_k$: As $d_k$ occurs as a summand in every $a_j - a_i$, $1 \le i \le k < k + 1 \le j \le n$, and in no other $a_j - a_i$, $1 \le i < j \le n$, it follows that $s = \sum_{k=1}^{n-1} k(n-k)d_k$.

Finally, as $\min_{1 \le k \le n-1} k(n-k) = n-1$ and $\max_{1 \le k \le n-1} k(n-k) = \lfloor \frac{1}{2}n \rfloor \lfloor \frac{1}{2}(n+1) \rfloor$, it follows that
$$(n-1)d = \sum_{k=1}^{n-1} (n-1)d_k \le \underbrace{\sum_{k=1}^{n-1} k(n-k)d_k}_{=s} \le \sum_{k=1}^{n-1} \lfloor \frac{1}{2}n \rfloor \lfloor \frac{1}{2}(n+1) \rfloor d_k = \\ = \lfloor \frac{1}{2}n \rfloor \lfloor \frac{1}{2}(n+1) \rfloor d,$$
as desired. This ends the proof.