All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Not all are equal (Posted on 2011-12-03)
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

Comments: ( Back to comment list | You must be logged in to post comments.)
 Solution | Comment 4 of 8 |
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
 Posted by John Dounis on 2011-12-07 11:51:59

 Search: Search body:
Forums (0)