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 ?

[Dr Sardonicus]

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².

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 well-ordering of the positive integers

[R. Gerbicz]

Originally Posted by Dr Sardonicus

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


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².

Assuming (1) and (2) you can easily prove the n^2 bound. [ps. First thought that he needs a Sidon sequence: https://en.wikipedia.org/wiki/Sidon_sequence ]

Theorem a(n)>=2*n-1 for all n, this proves that a(1)+..+a(n)>=n^2.
Let t=a(n)
then for each x=1..floor((t-1)/2)
[you can handle the odd/even t seperately]
at most one term of x,t-x can be in the sequence, obviously, because
x+(t-x)=t would be a forbidden triplet.
Notice that with this we covered all integers from [1,t-1] exactly once, only missing one case where t=2*m and x=m, but in that case none of x,t-x can be in the sequence, because m+m=2*m would be a solution.

So seeing the number of terms: n-1<=floor((t-1)/2),
n<=floor((t+1)/2)<=(t+1)/2, from this

2*n-1<=t=a(n), what we needed.

[chris2be8]

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 2n-1 (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

[Batalov]

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.

[R. Gerbicz]

Originally Posted by Batalov

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.

I agree with you, I haven't seen that this is in the Homework Help.

[Dr Sardonicus]

Originally Posted by Batalov

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.

Oops. Of course, hints only for homework problems. I just didn't notice this was in Homework Help. The query didn't appear to be "homework or related." Perhaps this thread belongs in "Other Mathematical Topics" instead?

Funny thing, the post that drew my attention to this thread seems no longer to be here...

[Batalov]

Right, hmmmm... a post disappeared.

[chalsall]

Originally Posted by Batalov

Right, hmmmm... a post disappeared.

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.

Originally Posted by chalsall

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.

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 =)))))

[Uncwilly]

Originally Posted by samuel

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

I am glad you are beginning to understand that there is much more math than you realised. As you begin to progress, if you are willing to be taught, there are a number of folks here that lead you through. Be prepared to do a lot of reading and study. If RD Silverman says anything, listen to him. His requirements might be high, but you will be the better for it. Don't try to tell him he is wrong. You will lose and be the worse for it. Also, he might decide to never help you again.