Kvant Math Problem 620

Consider small values of $n$ first.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 9m40s
Source on kvant.digital

Problem

Let $x_1$, $x_2$, $\ldots$, $x_n$ be real numbers such that $x_1^2+x_2^2+\ldots+x_n^2=1$. Prove that the sum of the absolute values of $2^n$ numbers $$\pm x_1 \pm x_2 \pm \ldots \pm x_n$$ (with all possible combinations of the signs “$+$” and “$-$”) does not exceed $2^n$.

I. Kasakovskikh

Exploration

Consider small values of $n$ first. For $n=1$, the numbers are $\pm x_1$, and their sum of absolute values is $|x_1| + |-x_1| = 2|x_1| \le 2$, since $x_1^2=1$ implies $|x_1|\le 1$. For $n=2$, the numbers are $\pm x_1 \pm x_2$, giving four numbers: $x_1+x_2$, $x_1-x_2$, $-x_1+x_2$, $-x_1-x_2$. Their absolute values sum to $|x_1+x_2| + |x_1-x_2| + |-x_1+x_2| + |-x_1-x_2| = 2(|x_1+x_2| + |x_1-x_2|)$.

Testing extreme cases, if $x_1^2+x_2^2=1$, the maximum occurs when $x_1$ and $x_2$ are both $1$ or both $-1$; but then the sum of absolute values is $2(|1+1| + |1-1|) = 4$, which equals $2^2$. Random smaller numbers, like $x_1=x_2=1/2$, yield a smaller sum.

For general $n$, the sum over all $2^n$ sign combinations of absolute values should be bounded by $2^n$. The simplest conjecture is that the maximum is attained when each $x_i$ is $\pm 1$, scaled appropriately to satisfy $x_1^2+\dots+x_n^2=1$, that is, all $x_i$ equal to $1/\sqrt{n}$. Testing for $n=2$, $x_1=x_2=1/\sqrt{2}$ gives sum $2(|1/\sqrt{2}+1/\sqrt{2}| + |1/\sqrt{2}-1/\sqrt{2}|) = 2( \sqrt{2}+0) = 2\sqrt{2} < 4$. This supports the conjecture.

The likely key insight is to exploit symmetry and a recursive formula: if $S_n$ denotes the sum of absolute values for $n$ numbers, then

$$S_n(x_1,\dots,x_n) = \sum_{\epsilon_1,\dots,\epsilon_n = \pm 1} |\epsilon_1 x_1 + \dots + \epsilon_n x_n| = \sum_{\epsilon_n = \pm 1} \sum_{\epsilon_1,\dots,\epsilon_{n-1}} |\epsilon_1 x_1 + \dots + \epsilon_{n-1} x_{n-1} + \epsilon_n x_n|.$$

This reduces to $S_n = \sum_{\epsilon} (|A + x_n| + |A - x_n|)$, where $A$ ranges over sums for $n-1$ variables. The inequality $|A+x_n| + |A-x_n| \le 2\max(|A|,|x_n|)$ is promising, but the sharper bound is $|A+x_n| + |A-x_n| \le 2(|A|+|x_n|)$; recursively, the $2^n$ factor emerges. Verifying the base case $n=1$ is straightforward, and the recursion preserves the bound.

The delicate step is ensuring that the recursive inequality does not overcount and that the worst-case configuration indeed gives the bound $2^n$.

Problem Understanding

The problem asks to prove an inequality: for real numbers $x_1,\dots,x_n$ with sum of squares equal to one, the sum of the absolute values of all $2^n$ linear combinations with arbitrary $\pm$ signs is at most $2^n$. This is a Type B problem since the statement is already fixed and no classification or extremal value is requested. The core difficulty lies in handling the exponential number of terms and exploiting the constraint $x_1^2+\dots+x_n^2=1$ efficiently. The underlying geometric intuition is that the numbers $x_1,\dots,x_n$ lie on the unit sphere in $\mathbb{R}^n$, and the sum over all vertices of the hypercube weighted by absolute value cannot exceed $2^n$.

Proof Architecture

Lemma 1: For any real numbers $A$ and $B$, $|A+B| + |A-B| \le 2(|A|+|B|)$; this follows from considering all four sign combinations for $A$ and $B$ and using the triangle inequality.

Lemma 2: If $S_{n-1}$ denotes the sum of absolute values for $n-1$ numbers, then adding $x_n$ yields $S_n = \sum_{\epsilon_1,\dots,\epsilon_{n-1}} (| \epsilon_1 x_1 + \dots + \epsilon_{n-1} x_{n-1} + x_n| + |\epsilon_1 x_1 + \dots + \epsilon_{n-1} x_{n-1} - x_n|)$, which is bounded by $2 S_{n-1}$; the lemma follows from Lemma 1 applied termwise.

Lemma 3: $S_1 \le 2$; this is immediate since $|x_1| \le 1$.

The main argument: apply induction on $n$ using Lemmas 1-3. The hardest step is Lemma 2, where careless application of inequalities could produce a loose bound exceeding $2^n$; careful term-by-term handling ensures the exact factor.

Solution

We proceed by induction on $n$. For $n=1$, the only numbers are $x_1$ and $-x_1$, and their sum of absolute values is $|x_1| + |-x_1| = 2|x_1| \le 2$, establishing the base case.

Assume the claim holds for $n-1$ numbers, that is, for any real numbers $x_1,\dots,x_{n-1}$ satisfying $x_1^2+\dots+x_{n-1}^2 \le 1$, the sum of absolute values of all $2^{n-1}$ combinations is at most $2^{n-1}$. Consider real numbers $x_1,\dots,x_n$ with $x_1^2+\dots+x_n^2=1$. Denote

$$S_n = \sum_{\epsilon_1,\dots,\epsilon_n = \pm 1} |\epsilon_1 x_1 + \dots + \epsilon_n x_n|.$$

Group terms according to the last sign $\epsilon_n$:

$$S_n = \sum_{\epsilon_1,\dots,\epsilon_{n-1}} \left( |\epsilon_1 x_1 + \dots + \epsilon_{n-1} x_{n-1} + x_n| + |\epsilon_1 x_1 + \dots + \epsilon_{n-1} x_{n-1} - x_n| \right).$$

Applying Lemma 1 with $A = \epsilon_1 x_1 + \dots + \epsilon_{n-1} x_{n-1}$ and $B = x_n$ gives

$$|\epsilon_1 x_1 + \dots + \epsilon_{n-1} x_{n-1} + x_n| + |\epsilon_1 x_1 + \dots + \epsilon_{n-1} x_{n-1} - x_n| \le 2\max(|A|,|B|) \le 2(|A|+|B|) \le 2(|A|+|x_n|).$$

Summing over all $2^{n-1}$ choices of $(\epsilon_1,\dots,\epsilon_{n-1})$ yields

$$S_n \le 2 \sum_{\epsilon_1,\dots,\epsilon_{n-1}} |\epsilon_1 x_1 + \dots + \epsilon_{n-1} x_{n-1}| + 2 \sum_{\epsilon_1,\dots,\epsilon_{n-1}} |x_n| = 2 S_{n-1} + 2^{n} |x_n|.$$

Since $x_1^2+\dots+x_n^2=1$, we have $|x_n|\le 1$, and by the inductive hypothesis, $S_{n-1} \le 2^{n-1}$. Therefore

$$S_n \le 2 \cdot 2^{n-1} + 2^{n} |x_n| \le 2^n + 2^n |x_n|.$$

A more careful argument improves this: for any real numbers $A$ and $B$,

$$|A+B| + |A-B| \le 2 \sqrt{A^2+B^2}.$$

Applying this to each term in $S_n$ gives

$$S_n \le \sum_{\epsilon_1,\dots,\epsilon_{n-1}} 2 \sqrt{ (\epsilon_1 x_1 + \dots + \epsilon_{n-1} x_{n-1})^2 + x_n^2 }.$$

Using the convexity of $f(t) = \sqrt{t