Let $n\geqslant 2$ be a fixed integer. Consider $n$ real numbers $a_1,a_2,\ldots,a_n$ not all equal and let\[d:=\max_{1\leqslant i<j\leqslant n}|a_i-a_j|;\qquad s=\sum_{1\leqslant i<j\leqslant n}|a_i-a_j|.\]Determine in terms of $n{}$ the smalest and largest values the quotient $s/d$ may achieve. Selected from the Kvant Magazine
Problem
Source: Romania TST 2024 Day 1 P2
Tags: algebra, inequalities
31.07.2024 20:36
We will show that \[\lfloor \frac{n}{2}\rfloor \lceil \frac{n}{2}\rceil \geq \frac{\sum|a_i-a_j|}{\max{|a_i-a_j|}}\geq n-1\]Suppose that $a_1\leq a_2\leq ...\leq a_n$. For $k\in [0,n]$ and $l\in [0,\lceil \frac{n}{2}\rceil-1]$ \[\sum{|a_i-a_j|}=\sum{(n-2k-1)a_{ n-k}}=\sum{(n-2l-1)(a_{n-l}-a_{l+1})}\geq(n-1)(a_n-a_1)\]Let's prove the upper bound. If $n=2m,$ for $0\leq l\leq m-1$ \[\sum{|a_i-a_j|}=\sum{(2m-2l-1)(a_{n-l}-a_{l+1})}\leq \sum{(2m-2l-1)(a_n-a_1)}\]Since $a_n-a_1\geq a_{n-l}-a_{l+1}\iff a_n-a_{n-l}\geq a_1-a_{l+1}$ which is true. \[\sum{(2m-2l-1)}=2m^2-2(0+...+(m-1))-m=2m^2-m(m-1)-m=m^2=\lfloor \frac{2m}{2}\rfloor \lceil \frac{2m}{2}\rceil \]If $n=2m+1,$ then for $0\leq l\leq m$ \[\sum{|a_i-a_j|}=\sum{(2m-2l)(a_{n-l}-a_{l+1})\leq 2\sum{(m-l)(a_n-a_1)}}\]\[2\sum{(m-l)}=2m^2+2m-m(m+1)=m^2+m=\lfloor \frac{2m+1}{2}\rfloor \lceil \frac{2m+1}{2}\rceil \]For lower bound, equality holds when $(a_1,...,a_n)=(\underbrace{a_1,a_1,...,a_1}_{n-1 \ \text{times}},a_n)$ and for higher bound, equality holds when $(a_1,...,a_n)=(\underbrace{a_1,a_1,...,a_1}_{\lfloor \frac{n}{2} \rfloor \ \text{times}},\underbrace{a_n,a_n,...,a_n}_{\lceil \frac{n}{2} \rceil \ \text{times}})$ as desired.$\blacksquare$
01.08.2024 22:37
Case 1: $n = 2k$. WLOG let $a_{1} \le a_{2} \le \dots \le a_{2k}$ and define $d_{i} = a_{2k+1-i} - a_{i}$ for $i \in \{1,2, \dots ,k\}$ we have that $d = d_{1} \ge d_{2} \ge \dots \ge d_{k} \ge 0$ and $$s = (2k-1)a_{2k} + (2k-3)a_{2k-1} + \dots - (2k-1)a_{1} = (2k-1)d_{1} + (2k-3)d_{2} + \dots + d_{k}$$ So $k^{2} \ge \frac{s}{d} \ge 2k-1$ (by using $0 \le d_{i} \le d$). Upper bound is achieved when $a_{1} = a_{2} = \dots = a_{k} = x$ and $a_{k+1} = a_{k+2} = \dots = a_{2k} = y$ with $x < y$ and lower bound is achieved when $a_{2} = a_{3} = \dots a_{2k-1} = x$ with $a_{1} < x < a_{2k}$ Case 2: $n = 2k+1$. Keep the notations from case 1. We have that $$s = 2ka_{2k+1} + 2(k-1)a_{2k} + \dots + 2ka_{1} = 2kd_{1} + 2(k-1)d_{2} + \dots + 2d_{k}$$ So $k(k+1) \ge \frac{s}{d} \ge 2k$. For the upper bound take $a_{1} = a_{2} = \dots =\ a_{k} = x$ and $a_{k+2} = a_{k+3} = \dots = a_{2k+1} = y$ with $x < a_{k+1} < y$ and for the lower bound take $a_{2} = a_{3} = \dots = a_{2k}$ with $a_{1} < x < a_{2k+1}$.
02.08.2024 04:38
Above solutions are too complicated, here is a short one: Fix $M=\max a_i,$ $m=\min a_i,$ now $d$ is fixed. Since $s$ is linear for $\forall a_i,$ we can adjust it to the boundary value, now let there are $k$ value $m$ and $n-k$ value $M.$ Then $s/d =k(n-k).$ So obviously the maximum and minimum value are $\lfloor n/2\rfloor \cdot\lceil n/2\rceil $ and $n-1.\Box$