Problem:
Let the sum of a set of numbers be the sum of its elements. Let be a set of positive integers, none greater than . Suppose no two disjoint subsets of have the same sum. What is the largest sum a set with these properties can have?
Solution:
First we show that contains at most elements. Suppose otherwise. Then has at least or subsets of or fewer members. The sum of each of these subsets is at most (since , hence, by the Pigeonhole Principle, at least two of these sums are equal. If the subsets are disjoint, we are done; if not, then the removal of the common element(s) yields the desired contradiction.
Next we attempt to construct such a -element set , by choosing its elements as large as possible. Including and in leads to no contradiction, but if is also in , then (in view of the conditions on would be violated. Hence we must omit . No contradiction results from letting be a member of , but then since , and since . So we must settle for as the fifth element of . Indeed, satisfies the conditions of the problem, yielding or as the candidate for its solution.
Finally, to show that the maximum is indeed , suppose that the sum is more for another choice of . Observe that this set must also contain and , for if even the smallest of them is omitted, the maximum possible sum is achievable only by including and , but then . Having chosen and , we must exclude , as noted before. If is included, then we are limited to the sum of as above. If is not included, then even by including and (which we can't) we could not surpass since . Consequently, is indeed the maximum sum one can attain.
The problems on this page are the property of the MAA's American Mathematics Competitions