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

(In reply to re(2): Solution by Ady TZIDON)

Ady,

It's sometimes more difficult to prove something that seems absolutely obvious than something that looks a bit more tricky.

Even so, in this case you are quite right. I even had the components (a,b,c,d,e,f,g) written out under my original solution. It was just a matter of reading them in the correct order and not getting distracted by irrelevancies.

Posted by broll on 2011-12-08 13:52:12