20190429, 00:43  #1 
2^{2}·73 Posts 
finding min
if a1,a2,.......,an are positive integers
if randomly chosen two from this list, they cannot be equal, and if you add them up the sum cannot be another number on this list my question is what is the minimum value of a1+a2+ ....... +an ? Last fiddled with by samuel on 20190429 at 00:47 
20190429, 12:07  #2 
Feb 2017
Nowhere
4,517 Posts 
As I read it...
A sequence {a_{n}} of positive integers satisfies the two conditions 1) If i <> j then a_{i} <> a_{j} and 2) a_{i} + a_{j} <> a_{k} for all positive integers i, j, and k The question is, what is the minimum of the sum of the first n terms of such a sequence? I'm also assuming (3) The sequence {a_{n}} is strictly increasing. Obviously(*) any sequence of distinct positive integers can be rearranged into a strictly increasing sequence. Whether this arrangement always minimizes the sum of the first n terms is left as an exercise for the reader. This means, I'm too lazy (or insufficiently interested) to work it out myself :D The best I can think of offhand is a_{n} = 2n  1. It obviously satisfies the three conditions. The sum of the first n terms is n^{2}. Obviously, the sequence a_{n} = n is the best you can do with conditions (1) and (3) , and the sum of the first n terms is n(n+1)/2. (*) because the relation < is a wellordering of the positive integers 
20190429, 14:17  #3  
"Robert Gerbicz"
Oct 2005
Hungary
2·733 Posts 
Quote:
Theorem a(n)>=2*n1 for all n, this proves that a(1)+..+a(n)>=n^2. Let t=a(n) then for each x=1..floor((t1)/2) [you can handle the odd/even t seperately] at most one term of x,tx can be in the sequence, obviously, because x+(tx)=t would be a forbidden triplet. Notice that with this we covered all integers from [1,t1] exactly once, only missing one case where t=2*m and x=m, but in that case none of x,tx can be in the sequence, because m+m=2*m would be a solution. So seeing the number of terms: n1<=floor((t1)/2), n<=floor((t+1)/2)<=(t+1)/2, from this 2*n1<=t=a(n), what we needed. 

20190429, 15:42  #4 
Sep 2009
11111110111_{2} Posts 
A little mental arithmetic suggests the greedy sequence is:
1, 2, 4, 7, 10, 13, 16, 19, ... Where all terms except the second are 1 mod 3, so the sum of any two such terms will be 2 mod 3. But as Dr Sardonicus suggested 2n1 (ie successive odd numbers) does better, since the sum of two odd numbers is always even. I can't see any way to beat that. Chris 
20190429, 16:02  #5 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{3}·11·107 Posts 
Just a quick notice for homework help forum: posting a complete solution is not beneficial to the asker. Suppose this is a homework; yes, they can quickly turn it in without thinking, but the goal of homework is to develop a skill, not to turn in the answer.
Please post successive hints if possible. 
20190429, 16:21  #6  
"Robert Gerbicz"
Oct 2005
Hungary
2·733 Posts 
Quote:


20190429, 17:17  #7  
Feb 2017
Nowhere
4,517 Posts 
Quote:
Funny thing, the post that drew my attention to this thread seems no longer to be here... 

20190429, 19:49  #8 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
10010011001000_{2} Posts 
Right, hmmmm... a post disappeared.

20190429, 20:26  #9 
If I May
"Chris Halsall"
Sep 2002
Barbados
22542_{8} Posts 
Yeah. Mine. Moved into the "Posts that seem less than useless, or something like that" thread.
When I posted my response this thread wasn't under the "Homework help thread I find this all somewhat amusing. My apologies if other's don't. 
20190429, 22:37  #10  
7,673 Posts 
Quote:
i saw your post i wanted to reply but then changed mind this maybe weird but i do some diggin and see lot of math i never seen after someone posted a link to some pdf on the other post of mine, i never stumble upon something so complicated it starred at it and read thru many pdf and website but still dont understand, i guess there is a different between hs math and college math, i still do not know what lesbgesian integration is all about and as for this problem it was assigned for amc10/mathcounts prep but i have no clue how to tackle it but now with all the explanations i do now. thank you =))))) 

20190429, 23:22  #11  
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
10010101001010_{2} Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Finding Methuselah  MooMoo2  Lounge  19  20171029 05:52 
Need help finding the pattern...  WraithX  Other Mathematical Topics  17  20170110 19:57 
Finding omega(k) for 1<=k<=10^12  voidme  Factoring  6  20120423 17:02 
Finding a paper  CRGreathouse  Information & Answers  1  20100817 22:32 
Finding My Niche  storm5510  PrimeNet  3  20090826 07:26 