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

Home > Just Math
Not all are equal (Posted on 2011-12-03) Difficulty: 3 of 5
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

No Solution Yet Submitted by Ady TZIDON    
Rating: 5.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution 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

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information