1996 USAMO Problems/Problem 2

Problem

For any nonempty set $S$ of real numbers, let $\sigma(S)$ denote the sum of the elements of $S$ . Given a set $A$ of $n$ positive integers, consider the collection of all distinct sums $\sigma(S)$ as $S$ ranges over the nonempty subsets of $A$ . Prove that this collection of sums can be partitioned into $n$ classes so that in each class, the ratio of the largest sum to the smallest sum does not exceed 2.

Solution

Let set $A$ consist of the integers $a_1\le a_2\le a_3\le\dots\le a_n$ . For $k\ge 2$ , call $a_k$ greedy if $\sum_{i=1}^{k-1}a_i < a_k$ . Also call $a_1$ greedy. Now put all elements of $A$ into groups of consecutive terms in such a way that each group $G$ begins with a greedy term, call it $a_p$ , and ends on the term $a_{q-1}$ just before the next greedy term after $a_p$ . (If $a_p$ is the last greedy term, let $q-1=n$ .) We introduce some more terminology. A sum $\sigma(S)$ is said to "belong to" a group $G$ if $\max(S)\in G$ . Denote by $\mathcal{S}(G)$ the set of all sums belonging to $G$ .

We now show that we can divide $\mathcal{S}(G)$ into $|G|$ (the cardinality of $G$ ) 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 $\frac{\max{\mathcal{S}(G)}}{\min{\mathcal{S}(G)}}< 2^{|G|}=2^{q-p}$ . Note that $\max{\mathcal{S}(G)}=\sum_{i=1}^{q-1}a_i$ and $\min{\mathcal{S}(G)}=a_p.$ Taking note of that fact that $a_{p+1},a_{p+2},\dots,a_{q-1}$ are not greedy numbers, we write:

$\begin{align*} \max{\mathcal{S}}&=\sum_{i=1}^{q-1}a_i \\ &=a_{q-1}+\sum_{i=1}^{q-2}a_i \\ &\le 2\sum_{i=1}^{q-2}a_i\\ &\le 2^2\sum_{i=1}^{q-3}a_i\\ &\vdots\\ &\le 2^{q-p-1}\sum_{i=1}^{p}a_i\\ &= 2^{q-p-1}(\sum_{i=1}^{p-1}a_i + a_p)\\ &<2^{q-p-1}(2a_p)\\ &=2^{q-p}\min\mathcal{S} \end{align*}$

where the inequalities after the ellipses result from the fact that $a_p$ is a greedy number (which implies by definition that $\sum_{i=1}^{p-1}a_i<a_p$ ). This proves the desired inequality. Now we can prove the result in bold above. Divide $\mathcal{S}(G)$ into $|G|=q-p$ classes by taking those terms in $[a_p,2a_p)$ and placing them in the first class, taking those terms in $[2a_p,2^2a_p)$ and placing them in another, and so on, until we reach $[2^{q-p-1}a_p,2^{q-p}a_p)$ . The inequality we proved above shows that all of the sums in $\mathcal{S}(G)$ will fall in one of these classes, as the intervals into which the classes fall form a continuous range bounded by $\min\mathcal{S}(G)=a_p$ on the bottom and $2^{q-p}a_p>\max\mathcal{S}(G)$ 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 $n$ classes, because every term $a_i$ belongs to a group and in each group, there are as many classes as there are terms.

Page

Toolbox

Search

1996 USAMO Problems/Problem 2

Problem

Solution