USAMO 1996 Problem 2

Changed to the constructive proof on 2026/1/2.

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\).

========================================================

Proof:

Define $s_i:=x_1+\dots+x_i$. The following algorithm gives $n$ classes $[\ell_1,r_1],\dots,[\ell_n,r_n]$ that may overlap that satisfy the constraints, which clearly suffices.

Initially set $\ell_1=x_1$ and $r_1=x_1$. For $i=2,3,\dots,n$ there are two cases.

If $s_{i-1}<x_i$, then set $\ell_i=x_i$ and $r_i=s_i=s_{i-1}+x_i<2\ell_i$. Note that a gap $g_i=[s_{i-1}+1,x_i-1]$ is formed.

If $x_i\le s_{i-1}$, then set $\ell_i=r_i+1$ and $r_i=s_i$. No gap is formed. Could any new sum fall into any previous gaps? Every new sum must be at least $x_i$, and every previous gap stops at some $x_j-1<x_i$. Hence that is impossible, and every new sum is still covered.