Difference between revisions of "2012 USAMO Problems/Problem 6"
(→See Also) |
(→Note:) |
||
(11 intermediate revisions by the same user 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>. | ||
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>. | ||
+ | |||
+ | ==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== |
Latest revision as of 12:37, 21 June 2023
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. Since we also have that there are positive and negative terms for evens. Which then gives us: 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 and since is the only choice for
Note:
The proof to the last inequality is as follows: First we may rewrite this as being: Thus, (the second equation is because the sum of the binomial coefficient is ) Since for all and for all and , it is apparent that: must be true for all (because if we rewrite this we get .) For all however, we may use some logic to first layout a plan. Since for and , , we may say that whole sum will be less than because for all Plugging this inequality back in gives us: because of the fact that
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.