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
First of all we arrange the n numbers in an increasing order:
(where if we have an index i, then a(i)> a(i-1))
a1,a2,...a(i),an
have this order and because the numbers are distinct we can construct the set K with size n-1:
a(n) + a(1)
a(n) + a(2)
.
.
.
each item of this set is increasingly bigger that the maximum number of the first set(that is a(n)) and so it's unique.
Having costructing that then we can continue with the next set with size n-2:
a(n) + a(n-1) + a(1)
a(n) + a(n-1) + a(2)
a(n) + a(n-1) + a(3)
.
.
.
and so we can construct an increasingly larger set with size n-k where k = 0..(n-1).
summing the size of it's set we come across a very very smart fellow(mr. Gauss) :).
that is size S = n+(n-1)+...1+ = n*(n+1)/2.
Edited on December 8, 2011, 10:45 am
Solution
