For n real numbers $a_{1},\, a_{2},\, \ldots\, , a_{n},$ let $d$ denote the difference between the greatest and smallest of them and $S = \sum_{i<j}\left |a_i-a_j \right|.$ Prove that \[(n-1)d\le S\le\frac{n^{2}}{4}d\] and find when each equality holds.
Problem
Source: 21-st Iberoamerican Mathematical Olympiad
Tags: inequalities, inequalities unsolved
hipsishopsis
06.05.2007 12:16
Not totally sure, but this might be a solution.
Let $s_{1}, \dots, s_{n}$ be a sequence so that $a_{s_{1}}\le \dots \le a_{s_{n}}$. Considerer sum $S=\sum_{i<j}|a_{i}-a_{j}|$ and arbitrary $s_{i}, i \le n-1$. Because every pair of $a_{i}, a_{j}$ are counted exactly once $a_{s_{i}}-a_{s_{i}+1}$ is counted $i(n-i)$ times. This implies that we can permute the indices of sequence $(a),$ as we wish.
WLOG we can thus assume $a_{1}\ge a_{2}\ge \dots \ge a_{n}$ and write $S=\sum_{i < j}(a_{i}-a_{j})$.
Now define a sequence $b_{1}= a_{1}-a_{2}, b_{2}= a_{2}-a_{3}, \dots, b_{k}= a_{k}-a_{k+1}, k < n$.
In the sum $b_{1}$ appears $n-1$ times, $b_{2}$ appears $2(n-2)$ times and so on, in general $b_{k}$ appears $k(n-k)$ times.
The sum becomes $S = \sum_{i=1}^{n-1}i(n-i) b_{i}$.
Now let's see what happens if we modify $b_{j}, 1 \le j \le n-1$ by some length m.
$S' = j(n-j)(b_{j}+m)+\sum_{i \neq j, 1 \le i \le n-1}i(n-i) b_{i}$
$= S-j(n-j)b_{j}+j(n-j)(b_{j}+m) = S+j(n-j) m$.
On the other hand $d' = b_{j}+m+\sum_{i \neq j, 1 \le i \le n-1}b_{i}= d+m$.
Examining the difference $\epsilon' = \frac{n^{2}}{4}d'-S' = \frac{n^{2}}{4}d+\frac{n^{2}}{4}m-S-j(n-j) m = \epsilon+m(\frac{n^{2}}{4}-j(n-j))$.
Assuming $n \ge 2$ we have $m(\frac{n^{2}}{4}-j(n-j)) \ge 0$ when $m > 0$, strengthening the inequality and similarly weakening the inequality when $m < 0$.
Obviously when we weaken the inequality to its limit $b_{j}= 0$ for every j and $S = 0 = d$.
To construct every possible situation we can start from $b_{1}, \dots, b_{n}= 0$ and start adding some m to them.
To keep the equality we must have $m(\frac{n^{2}}{4}-j(n-j)) = 0$ Resulting $j=\frac{n}{2}$.
That is, only $b_{n/2}$, if it exists, may be greater than zero for the equality.
Now considering the other inequality, $(n-1) d \le S$:
We have $\epsilon' = S'-(n-1)d' = S+j(n-j)m-(n-1)d-(n-1)m = \epsilon+m(j(n-j)-n+1)$.
Like above, we have $m(j(n-j)-n+1)$ \ge 0 when $m > 0$, strengthening the inequality and weakening when $m < 0$.
Again, at its limit $(n-1)d = 0 = S$.
Here for the equality we want $m(j(n-j)-n+1) = 0$, which implies $j=1$ or $j=n-1$.
That is, only $b_{1}$ and $b_{n-1}$ may be greater than zero for the equality.
skuge
23.08.2007 07:00
1) WLOG $ a_{1}\leq a_{2}\leq ... a_{n}$ $ \left |a_{i}-a_{1}\right|+\left |a_{n}-a_{i}\right| =a_{n}-a_{1}=d$ $ S =\sum_{i < j\not\in\left\{1,n\right\}}\left |ai-aj\right|.+\sum (|a_{i}-a_{1}|+|a_{n}-a_{i}|)+a_{n}-a_{1}=$ $ (n-1)d+\sum_{i < j\not\in\left\{1,n\right\}}\left |ai-aj\right|\geq (n-1)d$ and the equality holds when $ a_{2}=a_{3}=...=a_{n-1}$ 2) If $ i\leq\frac{n}{2}$ and $ a_{i-1}=a_{1}$: $ \sum |a_{i}-a_{j}|\leq\sum |a_{1}-a_{j}|$ If $ i\geq\frac{n+2}{2}$ and $ a_{i+1}=a_{n}$: $ \sum |a_{i}-a_{j}|\geq\sum |a_{n}-a_{j}|$ with this smoothing you have that the equality holds when $ a_{1}=a_{2}=...=a_{\frac{n}{2}}$ y $ a_{\frac{n+2}{2}}=...=a_{n}$, and evidently doesn't hold for $ n$ odd.
xavi
23.08.2007 18:02
Suppose WLOG that $ a_{1}\leq ...\leq a_{n}$. Then $ S=(n-1)(a_{n}-a_{1})+\sum_{i=2}^{[n/2]}(n+1-2i)(a_{n+1-i}-a_{i})$. Hence, 1) $ (n-1)d\leq (n-1)d+\sum_{i=2}^{[n/2]}(n+1-2i)(a_{n+1-i}-a_{i})=S$, and 2) $ S\leq (n-1)d+\sum_{i=2}^{[n/2]}(n+1-2i)d\leq\frac{n^{4}}{4}d$.
Ankoganit
04.01.2016 08:34
Sorry for reviving , but doesn't the fact that $S$ is convex in each of $a_i$'s give an easier solution?
WolfusA
28.10.2018 17:30
It does only for searching maximum. With order $a_1\le a_2\le...\le a_n$ it suffices to prove this inequality for all $k=0,1,...,n$ where $a_1=...=a_k\wedge a_{k+1}=...=a_n$