mersenneforum.org finding min
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2019-04-29, 00:43 #1 samuel   "silent magician!!" Apr 2019 nowheresville califo 101 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 2019-04-29 at 00:47
 2019-04-29, 12:07 #2 Dr Sardonicus     Feb 2017 Nowhere 355210 Posts 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
2019-04-29, 14:17   #3
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

140910 Posts

Quote:
 Originally Posted by Dr Sardonicus 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.

 2019-04-29, 15:42 #4 chris2be8     Sep 2009 3·72·13 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 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
 2019-04-29, 16:02 #5 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3·3,041 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.
2019-04-29, 16:21   #6
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

1,409 Posts

Quote:
 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.

2019-04-29, 17:17   #7
Dr Sardonicus

Feb 2017
Nowhere

25·3·37 Posts

Quote:
 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...

 2019-04-29, 19:49 #8 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3·3,041 Posts Right, hmmmm... a post disappeared.
2019-04-29, 20:26   #9
chalsall
If I May

"Chris Halsall"
Sep 2002

2×4,643 Posts

Quote:
 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.

2019-04-29, 22:37   #10
samuel

"silent magician!!"
Apr 2019
nowheresville califo

101 Posts

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

2019-04-29, 23:22   #11
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

23·32·112 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post MooMoo2 Lounge 19 2017-10-29 05:52 WraithX Other Mathematical Topics 17 2017-01-10 19:57 voidme Factoring 6 2012-04-23 17:02 CRGreathouse Information & Answers 1 2010-08-17 22:32 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