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