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{nS_2} \leq S_1^2 + \frac{1}{2}\left\lfloor\frac{n^2}{4}\right\rfloor\left(\max_i a_i - \min_i a_i\right)^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 \leq \dots \leq a_n$ and $S_1 > 0$.

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

$$\mu \sqrt{\sigma^2 + \mu^2} \leq \mu^2 + \frac{1}{2}\left\lfloor\frac{n^2}{4}\right\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

$$\sigma^2 \leq \left\lfloor\frac{n^2}{4}\right\rfloor \frac{(a_n - a_1)^2}{n^2} + \frac{1}{4\mu^2}\left(\left\lfloor\frac{n^2}{4}\right\rfloor \frac{(a_n - a_1)^2}{n^2}\right)^2 \tag{$\star$}$$

since $\mu > 0$.

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

Since $\sigma^2_{\mathbf{x}}$ 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^2_{\mathbf{x}} = \frac{k(n - k)}{n^2}(b - a)^2.$$

Now, $(n - 2k)^2 \geq 0$ gives $k(n - k) \leq n^2/4$, forcing $k(n - k) \leq \lfloor n^2/4\rfloor$.

Thus, 

$$\max_{\mathbf{x} \in [a, b]^n} \sigma^2_{\mathbf{x}} \leq \left\lfloor\frac{n^2}{4}\right\rfloor \frac{(b - a)^2}{n^2}$$

and $\sigma^2 \leq \lfloor n^2/4\rfloor (a_n - a_1)^2/n^2$, from which ($\star$) follows directly. $\square$