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= | + | <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= | + | <cmath>\sum_{k=1}^{\frac{n}{2}} \binom{\frac{n}{2}}{k}\left(2^k - \binom{k}{k-1}\right)</cmath> |
− | + | And | |
− | + | <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 | + | <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
Contents
[hide]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 1
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
.
Solution 2
Let It is evident that
for evens because of the second equation and
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
:
since it will be
for any choice of A we pick, it will have to be greater than
which means we can either pick 0 negative
or
negatives for j positive terms which gives us:
and
And
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:
Thus, we may say that this holds to be true for all
since
grows faster than the sum. Note that equality holds when
for all i which occurs when
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.