Given n distinct positive numbers a1,a2,...,an.
We construct all the possible sums (from 1 to n terms).
Prove that among those 2^n1 sums there are at least n(n+1)/2 different ones.
Source: a problem from Soviet Union 1963 contest
The reference to 2^n1 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 20111204 04:09:59 