Problem
COM-B2-M04-P016 A Maximum Sum Without Repetition
Let \(A\) be a set of distinct positive integers, and suppose no two different nonempty subsets of \(A\) have the same sum. Prove that if \(A\) contains \(k\) numbers, then the sum of all numbers in \(A\) is at least \(2^k-1\).
Order the numbers increasingly and prove a lower bound for each next number using sums of previous numbers.
Let the sum of all numbers in \(A\) be \(S\). The set \(A\) has \(2^k\) subsets, including the empty subset. By the condition, the sums of different nonempty subsets are distinct; the empty subset has sum \(0\), which does not coincide with them because all numbers are positive.
Thus we obtain \(2^k\) distinct integer sums. Each of them lies between \(0\) and \(S\), and there are exactly \(S+1\) integers in this interval. Hence \(S+1\ge 2^k\), so \(S\ge 2^k-1\).
This problem is suitable for strong students after discussing greedy minimal choice; the statement requires careful handling of subset sums.