Kvant Math Problem 1083

Consider small values of $n$ to understand the inequality.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 2m22s
Source on kvant.digital

Problem

The largest of the non-negative numbers $a_1$, $a_2$, $\ldots$, $a_n$ is $a$.

  1. Prove the inequality $$\frac{a_1^2+a_2^2+\ldots+a_n^2}n\le\left(\frac{a_1+a_2+\ldots+a_n}{n}\right)^2+\frac{a^2}4$$
  2. When is equality achieved?

L. G. Khanin

Exploration

Consider small values of $n$ to understand the inequality. For $n=2$, let the numbers be $a_1$ and $a_2$ with $a_2 \ge a_1 \ge 0$ and $a_2 = a$. The inequality becomes

$\frac{a_1^2 + a_2^2}{2} \le \left(\frac{a_1 + a_2}{2}\right)^2 + \frac{a^2}{4}.$

Expanding the right-hand side,

$\left(\frac{a_1 + a_2}{2}\right)^2 + \frac{a_2^2}{4} = \frac{a_1^2 + 2a_1 a_2 + a_2^2}{4} + \frac{a_2^2}{4} = \frac{a_1^2 + 2a_1 a_2 + 2 a_2^2}{4}.$

The left-hand side is $\frac{a_1^2 + a_2^2}{2} = \frac{2a_1^2 + 2a_2^2}{4}$. Subtracting the left from the right gives

$\frac{a_1^2 + 2 a_1 a_2 + 2 a_2^2 - 2 a_1^2 - 2 a_2^2}{4} = \frac{-a_1^2 + 2 a_1 a_2}{4} = \frac{a_1(2a_2 - a_1)}{4} \ge 0,$

since $0 \le a_1 \le a_2$. This suggests the inequality is plausible.

Testing $n=3$ with $0,0,a$ gives $\frac{a^2}{3} \le \frac{a^2}{9} + \frac{a^2}{4} = \frac{13 a^2}{36} \approx 0.361 a^2$, while $\frac{a^2}{3} \approx 0.333 a^2$, which also holds.

Equality occurs for $n=2$ if $a_1 = 0$ or $a_1 = a_2$. For $n>2$, some pattern likely involves all numbers being $0$ except possibly one or two equal to $a$.

The crucial point is how to formalize the inequality in general $n$. Writing it as

$\frac{1}{n} \sum_{i=1}^n a_i^2 - \left(\frac{\sum a_i}{n}\right)^2 \le \frac{a^2}{4}$

suggests using variance-like expressions, since the left-hand side is $\frac{1}{n} \sum a_i^2 - \bar a^2 = \frac{1}{n} \sum (a_i - \bar a)^2$, i.e., the average squared deviation. The maximum of $\sum (a_i - \bar a)^2$ under $0 \le a_i \le a$ occurs when numbers are as far apart as possible: some $0$, some $a$, with at most two distinct values. This is the core insight.

Problem Understanding

The problem asks to prove an inequality for non-negative numbers $a_1, \dots, a_n$ whose maximum is $a$. The inequality bounds the average of the squares by the square of the average plus $a^2/4$. This is Type B because a single statement is to be proved. The core difficulty lies in controlling the dispersion of the numbers and showing the bound $\frac{a^2}{4}$ is sufficient. The equality case requires identifying the extremal arrangements that saturate the variance bound.

Proof Architecture

Lemma 1: For any real numbers $x_1, \dots, x_n$, the identity $\frac{1}{n} \sum x_i^2 - \left(\frac{\sum x_i}{n}\right)^2 = \frac{1}{2 n^2} \sum_{i,j} (x_i - x_j)^2$ holds, expressing the difference as the average of squared pairwise differences. This is true by direct expansion.

Lemma 2: Among numbers in $[0,a]$, the sum $\sum_{i,j} (a_i - a_j)^2$ is maximized when each $a_i$ equals either $0$ or $a$, because quadratic functions attain extrema at endpoints of intervals.

Lemma 3: For numbers $0 \le a_i \le a$ taking only $0$ or $a$, the sum $\sum_{i,j} (a_i - a_j)^2$ is $2 k (n-k) a^2$, where $k$ is the number of $a_i$ equal to $a$. This is computed combinatorially by counting differing pairs. The maximum occurs at $k = \lfloor n/2 \rfloor$ or $k = \lceil n/2 \rceil$, giving at most $n^2 a^2 / 2$.

Main argument: Combine Lemmas 1–3 to show $\frac{1}{n} \sum a_i^2 - (\bar a)^2 \le a^2/4$, then add $\bar a^2$ to both sides to obtain the inequality. Equality occurs only in the extremal configurations identified in Lemma 3 with $k = n/2$ if $n$ even or $k = (n \pm 1)/2$ if $n$ odd.

Solution

For numbers $a_1, \dots, a_n$, let $\bar a = \frac{1}{n} \sum_{i=1}^n a_i$. Then

$\frac{1}{n} \sum_{i=1}^n a_i^2 - \bar a^2 = \frac{1}{2 n^2} \sum_{i,j=1}^n (a_i - a_j)^2$

by expansion: $\sum_{i,j} (a_i - a_j)^2 = \sum_{i,j} (a_i^2 - 2 a_i a_j + a_j^2) = 2 n \sum a_i^2 - 2 (\sum a_i)^2$. Dividing both sides by $2 n^2$ gives the identity.

The sum of squared differences is maximal when each $a_i$ is either $0$ or $a$, because for $x \in [0,a]$, the function $(x - y)^2$ is convex in each variable, and a convex function over a compact interval attains its maximum at an endpoint. Denote by $k$ the number of $a_i$ equal to $a$. Then the number of pairs $(i,j)$ with $a_i \neq a_j$ is $2 k (n-k)$, and each such pair contributes $a^2$ to the sum. Therefore

$\sum_{i,j} (a_i - a_j)^2 = 2 k (n-k) a^2.$

The maximum of $k(n-k)$ for integer $k \in [0,n]$ occurs at $k = \lfloor n/2 \rfloor$ or $k = \lceil n/2 \rceil$, giving $k(n-k) \le n^2 /4$. Hence

$\frac{1}{2 n^2} \sum_{i,j} (a_i - a_j)^2 = \frac{1}{2 n^2} \cdot 2 k(n-k) a^2 = \frac{k(n-k)}{n^2} a^2 \le \frac{a^2}{4}.$

Adding $\bar a^2$ to both sides yields

$\frac{1}{n} \sum_{i=1}^n a_i^2 = \bar a^2 + \left(\frac{1}{n} \sum a_i^2 - \bar a^2\right) \le \bar a^2 + \frac{a^2}{4}.$

Equality occurs exactly when $k = n/2$ for even $n$, or $k = (n \pm 1)/2$ for odd $n$, and all numbers equal either $0$ or $a$. This completes the proof.

∎

Verification of Key Steps

The first delicate step is the identity

$\frac{1}{n} \sum a_i^2 - \bar a^2 = \frac{1}{2 n^2} \sum_{i,j} (a_i - a_j)^2.$

Expanding the right-hand side: $\sum_{i,j} (a_i - a_j)^2 = \sum_i \sum_j a_i^2 - 2 \sum_i \sum_j a_i a_j + \sum_i \sum_j a_j^2 = 2 n \sum a_i^2 - 2 (\sum a_i)^2$. Dividing by $2 n^2$ gives exactly $\frac{1}{n} \sum a_i^2 - \bar a^2$, confirming correctness.

The second delicate step is maximizing $k(n-k)$ over $k \in [0,n]$. The function $k(n-k) = n k - k^2$ is quadratic, concave down, with vertex at