74th NMO Selection Tests for BMO and IMO

The required minimum is $n-1$ and is achieved, for instance, by $a_1<a_2=\cdots =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=\cdots =a_{\lfloor n/2\rfloor }<a_{\lfloor n/2\rfloor +1}=\cdots =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 \cdots \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+\cdots +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 $$\begin{gathered} (n-1)d=\sum _{k=1}^{n-1}(n-1)d_k\le \underset{=s}{\underbrace{\sum _{k=1}^{n-1}k(n-k)d_k}}\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, \end{gathered}$$ as desired. This ends the proof.