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

(solution added.)
(Note:)
 
(13 intermediate revisions by 3 users not shown)
Line 9: Line 9:
 
Prove that for any positive number <math>\lambda</math>, the number of sets <math>A</math> satisfying <math>S_A \ge \lambda</math> is at most <math>2^{n - 3}/\lambda^2</math>.  For what choices of <math>x_1</math>, <math>x_2</math>, <math>\dots</math>, <math>x_n</math>, <math>\lambda</math> does equality hold?
 
Prove that for any positive number <math>\lambda</math>, the number of sets <math>A</math> satisfying <math>S_A \ge \lambda</math> is at most <math>2^{n - 3}/\lambda^2</math>.  For what choices of <math>x_1</math>, <math>x_2</math>, <math>\dots</math>, <math>x_n</math>, <math>\lambda</math> does equality hold?
  
==Solution==
+
==Solution 1==
 
For convenience, let <math>N=\{1,2,\dots,n\}</math>.
 
For convenience, let <math>N=\{1,2,\dots,n\}</math>.
  
 
Note that <math>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</math>, so the sum of the <math>x_i</math> taken two at a time is <math>-1/2</math>. Now consider the following sum:
 
Note that <math>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</math>, so the sum of the <math>x_i</math> taken two at a time is <math>-1/2</math>. Now consider the following sum:
  
<cmath>\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}.</cmath>
+
<cmath>\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}.</cmath>
  
 
Since <math>S_A^2\geq 0</math>, it follows that at most <math>2^{n-2}/\lambda^2</math> sets <math>A\subseteq N</math> have <math>|S_A|\geq \lambda</math>.
 
Since <math>S_A^2\geq 0</math>, it follows that at most <math>2^{n-2}/\lambda^2</math> sets <math>A\subseteq N</math> have <math>|S_A|\geq \lambda</math>.
Line 22: Line 22:
 
Note that if equality holds, every subset <math>A</math> of <math>N</math> has <math>S_A\in\{-\lambda,0,\lambda\}</math>. It immediately follows that <math>(x_1,x_2,\ldots , x_n)</math> is a permutation of <math>(\lambda,-\lambda,0,0,\ldots , 0)</math>. Since we know that <math>\sum_{i=1}^{n} x_i^2=1</math>, we have that <math>\lambda=1/\sqrt{2}</math>.
 
Note that if equality holds, every subset <math>A</math> of <math>N</math> has <math>S_A\in\{-\lambda,0,\lambda\}</math>. It immediately follows that <math>(x_1,x_2,\ldots , x_n)</math> is a permutation of <math>(\lambda,-\lambda,0,0,\ldots , 0)</math>. Since we know that <math>\sum_{i=1}^{n} x_i^2=1</math>, we have that <math>\lambda=1/\sqrt{2}</math>.
  
 +
==Solution 2==
 +
Let <math>x_i=x_1,x_2,...,x_n</math> It is evident that <math>x_i = \frac{(-1)^i}{\sqrt{n}}</math> for evens because of the second equation and <math>x_i=\frac{(-1)^i}{\sqrt{n-1}}</math> 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 <math>\lambda = \frac{1}{\sqrt{n}}</math>:
 +
since it will be
 +
<cmath>x_1 + x_2 + ... + x_n </cmath>
 +
for any choice of A we pick, it will have to be greater than <math>\frac{1}{\sqrt{n}}</math> which means we can either pick 0 negative <math>x_m</math> or <math>j-1</math> negatives for j positive terms. Since we also have that there are <math>\frac{n}{2}</math> positive and negative terms for evens. Which then gives us:
 +
<cmath>\sum_{k=1}^{\frac{n}{2}} \binom{\frac{n}{2}}{k}\sum_{i=0}^{k-1} \binom{\frac{n}{2}}{i}</cmath>
 +
and
 +
<cmath>\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)</cmath>
 +
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: <cmath>\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}</cmath>
 +
Thus, we may say that this holds to be true for all <math>n \ge 2</math> since <math>n2^{n-3}</math> grows faster than the sum. Note that equality holds when <math>S_A \in \{\lambda,0,-\lambda\}</math> for all i which occurs when <math>x_i= \frac{1}{\sqrt{2}},-\frac{1}{\sqrt{2}},0,....</math> and <math>\lambda = \frac{1}{\sqrt{2}}</math> since <math>S_A=\frac{1}{\sqrt{2}}</math> is the only choice for <math>S_A \ge \lambda</math>
 +
<math>\blacksquare</math>
 +
 +
==Note:==
 +
The proof to the last inequality is as follows:
 +
First we may rewrite this as being:
 +
<cmath>\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}</cmath>
 +
Thus,
 +
<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 n2^{n-3}</cmath>
 +
(the second equation is because the sum of the binomial coefficient is <math>2^{\frac{n}{2}} - 1</math>)
 +
<cmath>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}</cmath>
 +
Since <math>2^n - 2^{\frac{n}{2}} \le n2^{n-3}</math> for all <math>n \ge 8</math> and <math>\sum_{k=1}^{\frac{n}{2}} \binom{\frac{n}{2}}{k} \sum_{i=k}^{\frac{n}{2}} \binom{\frac{n}{2}}{i} \ge 0</math> for all <math>k</math> and <math>i</math>, it is apparent that:
 +
<cmath>\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}</cmath>
 +
must be true for all <math>n \ge 8</math>(because if we rewrite this we get <math>2^{\frac{n}{2}}\left(8-n\right) \le 8</math>.) For all <math>2 \le n < 8</math> however, we may use some logic to first layout a plan. Since for <math>n=6,n=4,</math> and <math>n=2</math>, <math>2^{n} - 2^{\frac{n}{2}} = n2^{n-3} + 1</math>, we may say that whole sum will be less than <math>n2^{n-3}</math> because <math>\sum_{k=1}^{\frac{n}{2}} \binom{\frac{n}{2}}{k} \sum_{i=k}^{\frac{n}{2}} \binom{\frac{n}{2}}{i} \ge 1</math> for all <math>n \ge 2</math> Plugging this inequality back in gives us:
 +
<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>
  
 
==See Also==
 
==See Also==
Line 27: Line 53:
  
 
{{USAMO newbox|year=2012|num-b=5|aftertext=|after=Last Problem}}
 
{{USAMO newbox|year=2012|num-b=5|aftertext=|after=Last Problem}}
 +
{{MAA Notice}}
 
[[Category:Olympiad Algebra Problems]]
 
[[Category:Olympiad Algebra Problems]]

Latest revision as of 13:37, 21 June 2023

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 $j-1$ negatives for j positive terms. Since we also have that there are $\frac{n}{2}$ positive and negative terms for evens. Which then 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$

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$

See Also

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

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