2012 USAMO Problems/Problem 6
Contents
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.