mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Homework Help

Reply
 
Thread Tools
Old 2019-04-29, 00:43   #1
samuel
 
"silent magician!!"
Apr 2019
nowheresville califo

101 Posts
Default 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 2019-04-29 at 00:47
samuel is offline   Reply With Quote
Old 2019-04-29, 12:07   #2
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

355210 Posts
Default

As I read it...

A sequence {an} of positive integers satisfies the two conditions

1) If i <> j then ai <> aj and

2) ai + aj <> ak 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 {an} 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 an = 2n - 1. It obviously satisfies the three conditions. The sum of the first n terms is n2.

Obviously, the sequence an = 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
Dr Sardonicus is offline   Reply With Quote
Old 2019-04-29, 14:17   #3
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

140910 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
As I read it...

A sequence {an} of positive integers satisfies the two conditions

1) If i <> j then ai <> aj and

2) ai + aj <> ak 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 an = 2n - 1. It obviously satisfies the three conditions. The sum of the first n terms is n2.
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.
R. Gerbicz is offline   Reply With Quote
Old 2019-04-29, 15:42   #4
chris2be8
 
chris2be8's Avatar
 
Sep 2009

3·72·13 Posts
Default

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
chris2be8 is offline   Reply With Quote
Old 2019-04-29, 16:02   #5
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3·3,041 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2019-04-29, 16:21   #6
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

1,409 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2019-04-29, 17:17   #7
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

25·3·37 Posts
Default

Quote:
Originally Posted by Batalov View Post
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...
Dr Sardonicus is offline   Reply With Quote
Old 2019-04-29, 19:49   #8
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3·3,041 Posts
Default

Right, hmmmm... a post disappeared.
Batalov is offline   Reply With Quote
Old 2019-04-29, 20:26   #9
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

2×4,643 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
chalsall is offline   Reply With Quote
Old 2019-04-29, 22:37   #10
samuel
 
"silent magician!!"
Apr 2019
nowheresville califo

101 Posts
Default

Quote:
Originally Posted by chalsall View Post
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 =)))))
samuel is offline   Reply With Quote
Old 2019-04-29, 23:22   #11
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

23·32·112 Posts
Default

Quote:
Originally Posted by samuel View Post
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.
Uncwilly is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Finding Methuselah MooMoo2 Lounge 19 2017-10-29 05:52
Need help finding the pattern... WraithX Other Mathematical Topics 17 2017-01-10 19:57
Finding omega(k) for 1<=k<=10^12 voidme Factoring 6 2012-04-23 17:02
Finding a paper CRGreathouse Information & Answers 1 2010-08-17 22:32
Finding My Niche storm5510 PrimeNet 3 2009-08-26 07:26

All times are UTC. The time now is 20:31.

Wed Oct 21 20:31:47 UTC 2020 up 41 days, 17:42, 0 users, load averages: 1.43, 1.50, 1.57

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.