AMM problem 12448

This is AMM problem 12448 that I solved with my friends Satvik Saha and Sohom Gupta.

Problem Statement -

Given real numbers $a_1,\dots ,a_n$. Prove

$$S_1\sqrt{n{S}_2}\le S_1^2+\frac{1}{2}\lfloor \frac{n^2}{4}\rfloor {(\underset{i}{max}{a}_i-\underset{i}{min}{a}_i)}^2$$

where $S_1=\sum _{i=1}^n{a}_i$ and $S_2=\sum _{i=1}^n{a}_i^2$.

Solution -

Without loss of generality, let $a_1\le \cdots \le a_n$ and $S_1>0$.

Setting $\mu =S_1/n$, we need to prove 

$$\mu \sqrt{{\sigma }^2+{\mu }^2}\le {\mu }^2+\frac{1}{2}\lfloor \frac{n^2}{4}\rfloor \frac{(a_n-a_1{)}^2}{n^2}$$

where ${\sigma }^2=\frac{1}{n}\sum _{i=1}^n(a_i-\mu {)}^2=\frac{S_2}{n}-{\mu }^2$.

Squaring both sides, this is equivalent to

$$\begin{array}{}\text{(}\star \text{)}& {\sigma }^2\le \lfloor \frac{n^2}{4}\rfloor \frac{(a_n-a_1{)}^2}{n^2}+\frac{1}{4{\mu }^2}{\left(\lfloor \frac{n^2}{4}\rfloor \frac{(a_n-a_1{)}^2}{n^2}\right)}^2\end{array}$$

since $\mu >0$.

Let ${\mu }_{\mathbf{x}}=\frac{1}{n}\sum _i{x}_i$ and ${\sigma }_{\mathbf{x}}^2=\frac{1}{n}\sum _i(x_i-{\mu }_{\mathbf{x}}{)}^2$ for real numbers $x_1,\dots ,x_n$.

Since ${\sigma }_{\mathbf{x}}^2$ is a smooth convex function of $\mathbf{x}$, it attains its maximum on $[a,b{]}^n$ at an extreme point, i.e. when all $x_i\in \{a,b\}$.

If exactly $k$ many $x_i$ are equal to $a$ and $n-k$ many are equal to $b$, we have

$${\sigma }_{\mathbf{x}}^2=\frac{k(n-k)}{n^2}(b-a{)}^2.$$

Now, $(n-2k{)}^2\ge 0$ gives $k(n-k)\le n^2/4$, forcing $k(n-k)\le \lfloor n^2/4\rfloor$.

Thus, 

$$\underset{\mathbf{x}\in [a,b{]}^n}{max}{\sigma }_{\mathbf{x}}^2\le \lfloor \frac{n^2}{4}\rfloor \frac{(b-a{)}^2}{n^2}$$

and ${\sigma }^2\le \lfloor n^2/4\rfloor (a_n-a_1{)}^2/n^2$, from which ($\star$) follows directly. $◻$