# An Inequality from a Mongolian Exam

### Problem ### Solution 1

With $a_i=x_i-A,$ $i=1,2,\ldots,2n-1,$ the inequality becomes

$\displaystyle 2\sum_{i=1}^{2n-1}a_i^2\ge \sum_{i=1}^{2n-1}(a_i-a_n)^2$

while $\displaystyle \sum_{i=1}^{2n-1}a_i=0.$ Squaring on the right,

\displaystyle\begin{align}2\sum_{i=1}^{2n-1}a_i^2&\ge \sum_{i=1}^{2n-1}a_i^2-2a_n\sum_{i=1}^{2n-1}a_i +\sum_{i=1}^{2n-1}a_n^2\\ &=\sum_{i=1}^{2n-1}a_i^2 +(2n-1)a_n^2 \end{align}

i.e., $\displaystyle \sum_{i=1}^{2n-1}a_i^2\ge (2n-1)a_n^2.$

Now, for $1,\ldots,i-1,$ define $a_i=a_n-b_i$ and $a_{n+i}=a_n+c_i,$ with all $b_i$ and $c_i$ non-negative.

Further,

\displaystyle\begin{align} 0&=\sum_{i=1}^{2n-1}a_i=0\\ &=\sum_{i=1}^{n-1}a_i + a_n + \sum_{i=n+1}^{2n-1}a_i\\ &=\sum_{i=1}^{n-1}(a_n-b_i) + a_n + \sum_{i=1}^{n-1}(a_n+c_i)\\ &=\sum_{i=1}^{n-1}(c_i-b_i)+(2n-1)a_n. \end{align}

so that $\displaystyle \sum_{i=1}^{n-1}(b_i-c_i)=(2n-1)a_n.$

Next, $\displaystyle \sum_{i=1}^{2n-1}a_i^2\ge (2n-1)a_n^2$ is equivalent to

$\displaystyle \sum_{i=1}^{n-1}b_i^2+\sum_{i=1}^{n-1}c_i^2\ge\frac{2}{2n-1}\left(\sum_{i=1}^{n-1}b_i-\sum_{i=1}^{n-1}c_i\right)^2.$

The above is equivalent to

\displaystyle\begin{align} &(2n-1)\left(\sum_{i=1}^{n-1}b_i^2+\sum_{i=1}^{n-1}c_i^2\right)+4\left(\sum_{i=1}^{n-1}b_i\right)\left(\sum_{i=1}^{n-1}c_i\right)\\ &\qquad\qquad\ge 2\left(\sum_{i=1}^{n-1}b_i\right)^2+2\left(\sum_{i=1}^{n-1}c_i\right)^2. \end{align}

However,

$\displaystyle \sum_{i=1}^{n-1}b_i^2+\sum_{i=1}^{n-1}c_i^2+4\left(\sum_{i=1}^{n-1}b_i\right)\left(\sum_{i=1}^{n-1}c_i\right)\ge 0$

while, by the AM-QM inequality,

\displaystyle\begin{align}(2n-2)\sum_{i=1}^{n-1}b_i^2&\ge 2\left(\sum_{i=1}^{n-1}b_i\right)^2,\\ (2n-2)\sum_{i=1}^{n-1}c_i^2&\ge 2\left(\sum_{i=1}^{n-1}c_i\right)^2. \end{align}

Equality is attained when all $\{b_i\}$ and $\{c_i\}$ are zero, i.e., when all $\{x_i\}$ are equal.

### Solution 2

For $n=1$, the inequality is trivially satisfied. Consider $n\gt 1$. Let $y_i=x_i-x_n$. The inequality can be simplified as follows:

\displaystyle \begin{align} &2E\left[(x-E[x])^2\right]\geq E\left[(x-x_n)^2\right] \\ &2E\left[(y-E[y])^2\right]\geq E\left[y^2\right] \\ &E\left[y^2\right]\geq 2E[y]^2. \end{align}

Here $E[\cdot]$ denotes the average or the expectation value.

Note, $y_n=0$, $y_i\geq 0~\text{for}~i>n$, and $y_i\leq 0~\text{for}~i\lt n$.

Let $y_{2n-k}=p_k~\text{and}~y_k=-q_k~\text{for}~k\in\{1,2,\ldots,n-1\}$.

Let $\displaystyle S_p=\sum_{i=1}^{n-1}p_i$ and $\displaystyle S_q=\sum_{i=1}^{n-1}q_i$. All $p's$ and $q's$ are non-negative, so also $S_p$ and $S_q$.

By Jensen's inequality,

\displaystyle \begin{align} &\sum_{i=1}^{n-1}p_i^2 \geq \frac{S_p^2}{n-1},\\ &\sum_{i=1}^{n-1}q_i^2 \geq \frac{S_q^2}{n-1}. \end{align}

Thus,

\displaystyle \begin{align} LHS&=E\left[y^2\right]=\frac{\sum_{i=1}^{2n-1} y_i^2}{2n-1} =\frac{\sum_{i=1}^{n-1}(p_i^2+q_i^2)}{2n-1} \\ &\geq\frac{S_p^2+S_q^2}{(n-1)(2n-1)} =\frac{2\left(S_p^2+S_q^2\right)}{(2n-2)(2n-1)}\geq \frac{2\left(S_p^2+S_q^2\right)}{(2n-1)^2} \\ &\geq\frac{2(S_p-S_q)^2}{(2n-1)^2} =2\left(\frac{\sum_{i=1}^{n-1}(p_i-q_i)}{2n-1}\right)^2 =2E[y]^2=RHS. \end{align}

### Acknowledgment

Leo Giugiuc has kindly posted this elegant problem at the CutTheKnotMath facebook page. The problem was proposed by Baasanjav Battsengel. Later Leo posted a solution of his (Solution 1.) Leo credits Amir Hossein Parvardi with bringing this problem to his attenetion.

Solution 2 is by Amit Itagi. 