1996 USAMO Problems/Problem 2
For any nonempty set of real numbers, let denote the sum of the elements of . Given a set of positive integers, consider the collection of all distinct sums as ranges over the nonempty subsets of . Prove that this collection of sums can be partitioned into classes so that in each class, the ratio of the largest sum to the smallest sum does not exceed 2.
Let set consist of the integers . For , call greedy if . Also call greedy. Now put all elements of into groups of consecutive terms in such a way that each group begins with a greedy term, call it , and ends on the term just before the next greedy term after . (If is the last greedy term, let .) We introduce some more terminology. A sum is said to "belong to" a group if . Denote by the set of all sums belonging to .
We now show that we can divide into (the cardinality of ) classes in such a way that the maximum and minimum sum belonging to each class differ by no more than a factor of 2. Using the previous notation, we first prove that . Note that and Taking note of that fact that are not greedy numbers, we write:
where the inequalities after the ellipses result from the fact that is a greedy number (which implies by definition that ). This proves the desired inequality. Now we can prove the result in bold above. Divide into classes by taking those terms in and placing them in the first class, taking those terms in and placing them in another, and so on, until we reach . The inequality we proved above shows that all of the sums in will fall in one of these classes, as the intervals into which the classes fall form a continuous range bounded by on the bottom and on the top. This proves the result in bold.
However, that clearly implies the desired conclusion, as every sum belongs to a group, and every sum belonging to a group is a member of a class. Moreover, there will be precisely classes, because every term belongs to a group and for each group , there are as many classes for as there are terms in .
We proceed to solve this problem by induction. Our base case is when has 1 integer - there is 1 class: itself.
Let now have elements, and assume it works for this case. We add , another element, to the set. WLOG, let be the maximum element. Note that has to be the maximum element of a class.
We always get a new class that works: being the maximum element. This way all elements including will be in that class if . When it also works since must be the maximum element from our WLOG condition above, so our induction step is done.
|1996 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAMO Problems and Solutions|