NMO Selection Tests

Without loss of generality, we can assume that $a_1 \le a_2 \le \dots \le a_n$, and denote $d_k = a_{k+1} - a_k$, for $k = 1, 2, \dots, n-1$. Then we have:
* $d_1 + d_2 + \dots + d_{n-1} = d$;
* $|a_j - a_i| = d_i + d_{i+1} + \dots + d_{j-1}$, for any $i < j$ with $i, j \in \{1, \dots, n\}$.
Denote by $n_k$ the number of pairs $(i, j)$, with $1 \le i < j \le n$, such that the interval $[a_k, a_{k+1}]$ is contained in $[a_i, a_j]$. Then the conditions imply $i \le k < k+1 \le j$, so there are $k$ possible choices for $i$ and $n-k$ possible choices for $j$. Thus, $n_k = k(n-k)$. Consequently,
$$S = \sum_{k=1}^{n-1} n_k d_k = \sum_{k=1}^{n-1} k(n-k) d_k. \qquad (1)$$

For any $k \in \{1, 2, \dots, n-1\}$, we have $k(n-k) \ge n-1$.
Indeed, $k(n-k) \ge n-1 \iff kn-k^2 \ge n-1 \iff (k-1)(n-k-1) \ge 0$, which holds for all $k$ in the stated range.
From (1) and this, it follows that
$$S \ge \sum_{k=1}^{n-1} (n-1)d_k = (n-1)d,$$
which proves the left inequality.
Equality holds for any $n \ge 2$ if and only if $a_1 \le a_2 = a_3 = \dots = a_{n-1} \le a_n$.

Using AM-GM inequality, we obtain $k(n-k) \le \frac{n^2}{4}$, for all $k \in \{1, 2, \dots, n-1\}$. Therefore,
$$S = \sum_{k=1}^{n-1} k(n-k)d_k \le \sum_{k=1}^{n-1} \frac{n^2}{4}d_k = \frac{n^2}{4}d, \qquad (3)$$
which proves the right inequality.
Since equality in the inequality $k(n-k) \le \frac{n^2}{4}$ holds when $k = n-k$, i.e., when $n = 2k$ (so $n$ is even), from (3) we deduce:

* If $d_k = 0$ for all $k = 1, \dots, n-1$, i.e., $a_1 = a_2 = \dots = a_n$, then equality holds for any $n \ge 2$.
* If there exists $t \in \{1, \dots, n-1\}$ such that $d_t \ne 0$, then:
* If $n$ is odd, the right inequality is strict.
* If $n$ is even, equality holds only if $t = n-t$ and $d_t = d$, i.e., $n = 2t$ and $a_1 = \dots = a_t \le a_{t+1} = a_{t+2} = \dots = a_{2t}$.

$$d = a_n - a_1 = (a_n - a_k) + (a_k - a_1), \quad \text{for any } 2 \le k \le n-1.$$
We obtain:
$$\begin{aligned} S &= \sum_{1 \le i < j \le n} |a_j - a_i| = (a_n - a_1) + \sum_{k=2}^{n-1} ((a_n - a_k) + (a_k - a_1)) + \\ &\quad + \sum_{2 \le i < j \le n-1} |a_j - a_i| \\ &= (n-1)d + \sum_{2 \le i < j \le n-1} |a_j - a_i| \ge (n-1)d. \end{aligned}$$
If $n=2$ or $n=3$, equality holds for any numbers $a_1 \le a_2$, respectively $a_1 \le a_2 \le a_3$.
If $n \ge 4$, equality holds if and only if $a_1 \le a_2 = a_3 = \dots = a_{n-1} \le a_n$.

Alternative solution for the right inequality.
We prove by induction the statement:
$$P(n): \quad \sum_{1 \le i < j \le n} |a_j - a_i| \le \frac{n^2}{4} \cdot \max_{1 \le i < j \le n} |a_j - a_i|,$$
for all $n \ge 2$ and any real numbers $a_1, a_2, \dots, a_n$. Without loss of generality, assume $a_1 \le a_2 \le \dots \le a_n$.
Base cases:
$$P(2): \quad a_2 - a_1 \le \frac{2^2}{4} \cdot (a_2 - a_1) \iff a_2 - a_1 \le a_2 - a_1,$$
$$P(3): \quad (a_2 - a_1) + (a_3 - a_2) + (a_3 - a_1) \le \frac{3^2}{4} \cdot (a_3 - a_1) \iff 2(a_3 - a_1) \le \frac{9}{4}(a_3 - a_1).$$

Assume $P(n-2)$ holds for some $n \ge 4$. Using the notation from the statement and the fact that
$$d = a_n - a_1 = (a_n - a_k) + (a_k - a_1), \quad \text{for any } 2 \le k \le n-1,$$
we deduce:
$$S = \sum_{1 \le i < j \le n} |a_j - a_i| = (n-1)d + \sum_{2 \le i < j \le n-1} |a_j - a_i|.$$
Denote
$$S' = \sum_{2 \le i < j \le n-1} |a_j - a_i|, \quad d' = a_{n-1} - a_2.$$
Obviously, $d' \le d$. Since $P(n-2)$ holds, we get $S' \le \frac{(n-2)^2}{4} \cdot d'$. Therefore,
$$S = (n-1)d + S' \le (n-1)d + \frac{(n-2)^2}{4} \cdot d' \le (n-1)d + \frac{(n-2)^2}{4} \cdot d = \frac{n^2}{4} \cdot d,$$
which proves $P(n)$.
To determine when equality holds, observe that in $P(2)$ equality holds for any $a_1 \le a_2$, and in $P(3)$ equality holds only if $a_1 = a_2 = a_3$ (strict inequality otherwise if $a_1 < a_3$).
It is clear that if $a_1 = a_2 = \dots = a_n$, then equality holds in $P(n)$ for any $n \ge 2$.
Assume now that $a_1 < a_n$. From the previous inequality, equality in $P(n)$ holds if and only if equality holds in $P(n-2)$ and $d' = d$. Consequently:
* if $n$ is odd, the inequality $P(n)$ is strict;
* if $n$ is even, say $n = 2t$, equality holds if and only if $a_1 = a_2 = \dots = a_t < a_{t+1} = a_{t+2} = \dots = a_{2t}$.