Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2012 USAMO Problems/Problem 6"
(→‎Solution 2)
Line 28: Line 28:
 
<cmath>x_1 + x_2 + ... + x_n </cmath>
 
<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>\frac{j}{2}-1</math> negatives for j positive terms  which gives us:
 
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>\frac{j}{2}-1</math> negatives for j positive terms  which gives us:
−
<cmath>\sum_{k=0}^{\frac{n}{2}-1} \sum_{i=0}^{\frac{n}{2}-k-1} \binom{\frac{n}{2} - k-1}{i}</cmath>
+
<cmath>\sum_{k=1}^{\frac{n}{2}} \binom{\frac{n}{2}}{k}\sum_{i=0}^{\frac{n}{2}-1} \binom{k}{i}</cmath>
 
and  
 
and  
−
<cmath>\sum_{k=0}^{\frac{n}{2} - 1} 2^{\frac{n}{2} - k - 1}</cmath>
+
<cmath>\sum_{k=1}^{\frac{n}{2}} \binom{\frac{n}{2}}{k}\left(2^k - \binom{k}{k-1}\right)</cmath>
−
Thus, we have <math>2^{\frac{n}{2}} - 1</math> choices for our set A for even values:
+
And
−
<cmath>2^{\frac{n}{2}}-1 \le n2^{n-3}</cmath>
+
<cmath>\sum_{k=1}^{\frac{n}{2}} \binom{\frac{n}{2}}{k}\left(2^k - k\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:
 
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>2^{\lfloor\frac{n}{2}\rfloor}-1 \le n2^{n-3}</cmath>
+
<cmath>\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor} \binom{\lfloor\frac{n}{2}\rfloor}{k}\left(2^k - k\right) \le n2^{n-3}</cmath>
−
Thus, we may say that this holds to be true for all <math>n \ge 2</math>. 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>
+
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>
 
<math>\blacksquare</math>
 
<math>\blacksquare</math>
 +
 
==See Also==
 
==See Also==
 
*[[USAMO Problems and Solutions]]
 
*[[USAMO Problems and Solutions]]

Revision as of 11:50, 12 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}^{\frac{n}{2}-1} \binom{k}{i}\] and \[\sum_{k=1}^{\frac{n}{2}} \binom{\frac{n}{2}}{k}\left(2^k - \binom{k}{k-1}\right)\] And \[\sum_{k=1}^{\frac{n}{2}} \binom{\frac{n}{2}}{k}\left(2^k - k\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^k - k\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,....$ $\blacksquare$

See Also

2012 USAMO (Problems • Resources)
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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2012_USAMO_Problems/Problem_6&oldid=183898"