Difference between revisions of "2012 USAMO Problems/Problem 6"

Revision as of 21:22, 13 December 2022

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<j\leq n} x_ix_j=\left(\sum_{i=1}^{n}x_i\right)^2-\left(\sum_{j=1}^{n} x_i^2\right)=-1$ , so the sum of the $x_i$ taken two at a time is $-1/2$ . Now consider the following sum:

$\sum_{A\subseteq N}S_A^2=2^{n-1}\left(\sum_{j=1}^{n} x_i^2\right)+2^{n-1}\left(\sum_{1\leq i<j\leq n} x_ix_j\right)=2^{n-2}.$

Since $S_A^2\geq 0$ , it follows that at most $2^{n-2}/\lambda^2$ sets $A\subseteq N$ have $|S_A|\geq \lambda$ .

Now note that $S_A+S_{N/A}=0$ . It follows that at most half of the $S_A$ such that $|S_A|\geq\lambda$ are positive. This shows that at most $2^{n-3}/\lambda^2$ sets $A\subseteq N$ satisfy $S_A\geq \lambda$ .

Note that if equality holds, every subset $A$ of $N$ has $S_A\in\{-\lambda,0,\lambda\}$ . It immediately follows that $(x_1,x_2,\ldots , x_n)$ is a permutation of $(\lambda,-\lambda,0,0,\ldots , 0)$ . Since we know that $\sum_{i=1}^{n} x_i^2=1$ , we have that $\lambda=1/\sqrt{2}$ .

Solution 2

Let $x_i=x_1,x_2,...,x_n$ It is evident that $x_i = \frac{(-1)^i}{\sqrt{n}}$ for evens because of the second equation and $x_i=\frac{(-1)^i}{\sqrt{n-1}}$ for odds(one term will be 0 to maintain the first condition). We may then try and get an expression for the maximum number of sets that satisfy this which occur when $\lambda = \frac{1}{\sqrt{n}}$ : since it will be $x_1 + x_2 + ... + x_n$ for any choice of A we pick, it will have to be greater than $\frac{1}{\sqrt{n}}$ which means we can either pick 0 negative $x_m$ or $\frac{j}{2}-1$ negatives for j positive terms which gives us: $\sum_{k=1}^{\frac{n}{2}} \binom{\frac{n}{2}}{k}\sum_{i=0}^{k-1} \binom{\frac{n}{2}}{i}$ and $\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)$ For odd values, let it be the same as the last even valued sequence where n is even(i.e. the same as the sequence before it but with an extra 0 in one of the spots). Then, the following is apparent: $\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor}\binom{\lfloor \frac{n}{2}\rfloor}{k}\left(2^{\lfloor\frac{n}{2}\rfloor} - \sum_{i=k}^{\lfloor\frac{n}{2}\rfloor}\binom{\lfloor \frac{n}{2}\rfloor}{i}\right) \le n2^{n-3}$ Thus, we may say that this holds to be true for all $n \ge 2$ since $n2^{n-3}$ grows faster than the sum. Note that equality holds when $S_A \in \{\lambda,0,-\lambda\}$ for all i which occurs when $x_i= \frac{1}{\sqrt{2}},-\frac{1}{\sqrt{2}},0,....$ and $\lambda = \frac{1}{\sqrt{2}}$ since $S_A=\frac{1}{\sqrt{2}}$ is the only choice for $S_A \ge \lambda$ $\blacksquare$ Mathiscool109 (talk) 21:20, 13 December 2022 (EST)

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$ Mathiscool109 (talk) 21:22, 13 December 2022 (EST)

@@ Line 49: / Line 49: @@
 <cmath>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}</cmath>
 because of the fact that <math>- \sum_{k=1}^{\frac{n}{2}} \binom{\frac{n}{2}}{k} \sum_{i=k}^{\frac{n}{2}} \binom{\frac{n}{2}}{i} \le -1</math>
+[[User:Mathiscool109|Mathiscool109]] ([[User talk:Mathiscool109|talk]]) 21:22, 13 December 2022 (EST)
 ==See Also==

2012 USAMO (Problems • Resources)
Preceded by Problem 5	Last Problem
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search