USAMO 96/A2 solution

25th USAMO 1996

Problem A2

Let S be a set of n positive integers. Let P be the set of all integers which are the sum of one or more distinct elements of S. Show that we can find n subsets of P whose union is P such that if a, b belong to the same subset, then a ≤ 2b.

Solution

Let the members of S be a₁ < a₂ < ... < a_n. Let s_m = a₁ + a₂ + ... + a_m and put s₀ = 0. Let P_m = { s ∈ P : s_m-1 < s ≤ s_m } for m = 1, 2, ... , n. We claim that this partition works. It is sufficient to show that if b ∈ P_m then 2b > s_m (for then if a also belongs to P_m we have a ≤ s_m <= 2b).

Now since b > s_m-1, b must be a sum which includes some a_i with i ≥ m. So certainly b ≥ a_i ≥ a_m = s_m - s_m-1 > s_m - b. Hence 2b > s_m as required.

25th USAMO 1996