75th NMO Selection Tests

Without loss of generality, we can assume that $a_1\le a_2\le \cdots \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+\cdots +d_{n-1}=d$; $|a_j-a_i|=d_i+d_{i+1}+\cdots +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.(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⟺kn-k^2\ge n-1⟺(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=\cdots =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,(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=\cdots =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=\cdots =a_t\le a_{t+1}=a_{t+2}=\cdots =a_{2t}$.

$$d=a_n-a_1=(a_n-a_k)+(a_k-a_1),\text{for any }2\le k\le n-1.$$ We obtain: $$\begin{array}{rl}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))+\\ & +\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{array}$$ 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=\cdots =a_{n-1}\le a_n$.

Alternative solution for the right inequality. We prove by induction the statement: $$P(n):\sum _{1\le i<j\le n}|a_j-a_i|\le \frac{n^2}{4}\cdot \underset{1\le i<j\le n}{\max }|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 \cdots \le a_n$. Base cases: $$P(2):a_2-a_1\le \frac{2^2}{4}\cdot (a_2-a_1)⟺a_2-a_1\le a_2-a_1,$$ $$P(3):(a_2-a_1)+(a_3-a_2)+(a_3-a_1)\le \frac{3^2}{4}\cdot (a_3-a_1)⟺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),\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^{\prime }=\sum _{2\le i<j\le n-1}|a_j-a_i|,d^{\prime }=a_{n-1}-a_2.$$ Obviously, $d^{\prime }\le d$. Since $P(n-2)$ holds, we get $S^{\prime }\le \frac{(n-2{)}^2}{4}\cdot d^{\prime }$. Therefore, $$S=(n-1)d+S^{\prime }\le (n-1)d+\frac{(n-2{)}^2}{4}\cdot d^{\prime }\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=\cdots =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^{\prime }=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=\cdots =a_t<a_{t+1}=a_{t+2}=\cdots =a_{2t}$.