Задача из журнала «Квант» (1970 год, 11 выпуск)
Условие
Докажите, что если разность между наибольшим и наименьшим из $n$ вещественных чисел $a_1, a_2, \ldots, a_n$ равна $d$, а сумма модулей всех $\frac{n(n-1)}{2}$ попарных разностей этих чисел $\sum\limits_{i<j}|a_i — a_j|$ равна $s$, то $(n-1)$ $d\leqslant s\leqslant \frac{n^2}{4}d$.
Решение
Нанесем точки $a_1, a_2, \ldots, a_n$ на числовую ось. Тогда $d$ — расстояние между крайними из этих точек, самой левой и самой правой, а $\sum\limits_{i<j}|a_i — a_j|$ — сумма всех попарных расстояний между этими точками. Можно, очевидно, считать, что точки обозначены через $a_1, a_2, \ldots, a_n$ в порядке возрастания: $a_1 \leqslant a_2\leqslant \ldots \leqslant a_n$ (рисунок). Обозначим расстояние между соседними точками $a_k$ и $a_{k+1}$ через $d_k(k=1, 2, \ldots, n-1)$. Очевидно, $$d=d_1+d_2 \ldots +d_{n-1}.$$ Выразим теперь $s$ через величины $d_k$. Для этого заменим в сумме $s$ длину каждого отрезка $|a_i-a_j|$ суммой тех $d_k$, из которых он состоит: $|a_i-a_j|=d_i+d_{i+1}+\ldots+d_{j-1}$. Ясно, что $d_k$ входит в те отрезки, у которых левый конец лежит в одной из точек $a_1,\ldots, a_k$, а правый — в одной из точек $a_{k+1}, \ldots a_n$, то есть в общей сложности $d_k$ входит в сумму $k(n-k)$ раз. Поэтому $$s=\sum\limits_{k=1}^{n-1}k(n-k)d_k.$$ Теперь доказываемое утверждение следует из двух совсем простых неравенств: для всех $k=1, \ldots, n-1$
- $k(n-k)\geqslant n-1\Leftrightarrow kn-k^2-n+1\geqslant 0 \Leftrightarrow (k-1)(n-k-1)\geqslant 0$
- $k(n-k)\leqslant\frac{n^2}{4}\Leftrightarrow n^2-4nk+4k^2\geqslant 0 \Leftrightarrow\left(n-2k\right)^2$
Пользуясь этими оценками $$\sum\limits_{k=1}^{n-1}k(n-k)d_k\geqslant \sum\limits_{k=1}^{n-1}(n-1)d_k=(n-1)d,$$ $$\sum\limits_{k=1}^{n-1}k(n-k)d_k\leqslant\sum\limits_{k=1}^{n-1}\frac{n^2}{4}d_k=\frac{n^2}{4}d.$$
Интересно выяснить
Являются ли указанные в условии задачи оценки точными, нельзя ли, скажем, вместо $n-1$ поставить в левом неравенстве большее число? Для того, чтобы убедиться в противном, достаточно привести пример такого случая, когда неравенство превращается в равенство (причем в обеих его частях стоят положительные числа). Такой пример легко придумать, разобравшись в нашем доказательстве: нужно расположить точки $a_1, a_2, \ldots, a_n$ так, чтобы все $d_k$, кроме первого — $d_1$, равнялись нулю, то есть взять $a_1 < a_2 = a_3 = \ldots = a_n$. Тогда $s = (n-1)d_1 = (n-1)d$.
Что касается второго неравенства $s\leqslant \frac{n^2}{4} d$, то при четном $n = 2m$ в нем тоже может достигаться равенство (достаточно взять $a_1 = a_2 = \ldots = a_m \lt a_{m+1} = \ldots = a_2m)$, а при нечетном $n = 2m + 1$ его можно несколько уточнить: нетрудно сообразить, что при нечетном $n$ наибольшее из чисел $k(n-k)$ равно $\frac{n-1}{2} \times \frac{n+1}{2} = \frac{n^2-1}{4}$; пользуясь этим вместо неравенства б), можно так же, как и выше, доказать более сильное неравенство $s \lt \frac{n^2-1}{4}d$. Равенство в нем достигается, когда $a_1 = \ldots = a_m \lt a_{m+1} = \ldots = a_{2m+1}$.