Difference between revisions of "2012 USAMO Problems/Problem 6"
(solution added.) |
(→Solution) |
||
Line 14: | Line 14: | ||
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} | + | <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 21: | Line 21: | ||
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>. | ||
− | |||
==See Also== | ==See Also== |
Revision as of 19:23, 10 December 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 |