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
(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 20111208 13:52:12 