Given n distinct positive numbers a1,a2,...,an.
We construct all the possible sums (from 1 to n terms).

Prove that among those 2^n-1 sums there are at least n(n+1)/2 different ones.

Source: a problem from Soviet Union 1963 contest

The reference to 2^n-1 sums seems unnecessary. There are n numbers from 1 to n so the largest number that can be obtained is clearly the nth triangular number; indeed this is true by definition. And since we are combining the numbers in all possible ways, it must equally be possible to obtain each of the n(n+1)/2 sums.

Edited on December 4, 2011, 4:18 am

Posted by broll on 2011-12-04 04:09:59