# 2012 USAMO Problems/Problem 6

## Problem

For integer $n \ge 2$, let $x_1$, $x_2$, $\dots$, $x_n$ be real numbers satisfying $$x_1 + x_2 + \dots + x_n = 0, \quad \text{and} \quad x_1^2 + x_2^2 + \dots + x_n^2 = 1.$$ For each subset $A \subseteq \{1, 2, \dots, n\}$, define $$S_A = \sum_{i \in A} x_i.$$ (If $A$ is the empty set, then $S_A = 0$.)

Prove that for any positive number $\lambda$, the number of sets $A$ satisfying $S_A \ge \lambda$ is at most $2^{n - 3}/\lambda^2$. For what choices of $x_1$, $x_2$, $\dots$, $x_n$, $\lambda$ does equality hold?

## Solution 1

For convenience, let $N=\{1,2,\dots,n\}$.

Note that $2\sum_{1\leq i, so the sum of the $x_i$ taken two at a time is $-1/2$. Now consider the following sum:

## Note:

The proof to the last inequality is as follows: First we may rewrite this as being: $$\sum_{k=1}^{\frac{n}{2}} \binom{\frac{n}{2}}{k} \left( 2^{\frac{n}{2}} - \sum_{i=k}^{\frac{n}{2}} \binom{\frac{n}{2}}{i}\right) \le n2^{n-3}$$ Thus, $$2^n - 2^{\frac{n}{2}} - \sum_{k=1}^{\frac{n}{2}} \binom{\frac{n}{2}}{k} \sum_{i=k}^{\frac{n}{2}} \binom{\frac{n}{2}}{i} \le n2^{n-3}$$ (the second equation is because the sum of the binomial coefficient is $2^{\frac{n}{2}} - 1$) $$2^n - 2^{\frac{n}{2}} \le n2^{n-3} + \sum_{k=1}^{\frac{n}{2}} \binom{\frac{n}{2}}{k} \sum_{i=k}^{\frac{n}{2}} \binom{\frac{n}{2}}{i}$$ Since $2^n - 2^{\frac{n}{2}} \le n2^{n-3}$ for all $n \ge 8$ and $\sum_{k=1}^{\frac{n}{2}} \binom{\frac{n}{2}}{k} \sum_{i=k}^{\frac{n}{2}} \binom{\frac{n}{2}}{i} \ge 0$ for all $k$ and $i$, it is apparent that: $$\sum_{k=1}^{\frac{n}{2}} \binom{\frac{n}{2}}{k} \sum_{i=0}^{k-1} \binom{\frac{n}{2}}{i} \le n2^{n-3}$$ must be true for all $n \ge 8$(because if we rewrite this we get $2^{\frac{n}{2}}\left(8-n\right) \le 8$.) For all $2 \le n < 8$ however, we may use some logic to first layout a plan. Since for $n=6,n=4,$ and $n=2$, $2^{n} - 2^{\frac{n}{2}} = n2^{n-3} + 1$, we may say that whole sum will be less than $n2^{n-3}$ because $\sum_{k=1}^{\frac{n}{2}} \binom{\frac{n}{2}}{k} \sum_{i=k}^{\frac{n}{2}} \binom{\frac{n}{2}}{i} \ge 1$ for all $n \ge 2$ Plugging this inequality back in gives us: $$2^{n} - 2^{\frac{n}{2}} - \sum_{k=1}^{\frac{n}{2}} \binom{\frac{n}{2}}{k} \sum_{i=k}^{\frac{n}{2}} \binom{\frac{n}{2}}{i} \le 2^{n} - 2^{\frac{n}{2}} - 1 = n2^{n-3}$$ because of the fact that $- \sum_{k=1}^{\frac{n}{2}} \binom{\frac{n}{2}}{k} \sum_{i=k}^{\frac{n}{2}} \binom{\frac{n}{2}}{i} \le -1$

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 