Difference between revisions of "2012 USAMO Problems/Problem 6"
m (→See also) |
(solution added.) |
||
Line 10: | Line 10: | ||
==Solution== | ==Solution== | ||
+ | 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: | ||
+ | |||
+ | <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>. | ||
+ | |||
+ | Now note that <math>S_A+S_{N/A}=0</math>. It follows that at most half of the <math>S_A</math> such that <math>|S_A|\geq\lambda</math> are positive. This shows that at most <math>2^{n-3}/\lambda^2</math> sets <math>A\subseteq N</math> satisfy <math>S_A\geq \lambda</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>. | ||
+ | |||
==See Also== | ==See Also== |
Revision as of 12:35, 17 September 2012
Problem
For integer , let , , , be real numbers satisfying For each subset , define (If is the empty set, then .)
Prove that for any positive number , the number of sets satisfying is at most . For what choices of , , , , does equality hold?
Solution
For convenience, let .
Note that , so the sum of the taken two at a time is . Now consider the following sum:
Since , it follows that at most sets have .
Now note that . It follows that at most half of the such that are positive. This shows that at most sets satisfy .
Note that if equality holds, every subset of has . It immediately follows that is a permutation of . Since we know that , we have that .
See Also
2012 USAMO (Problems • Resources) | ||
Preceded by Problem 5 |
Last Problem | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |