|
On September 03 2011 02:09 whistle wrote:
Don't really have an answer and I'm not too good at math riddles, but here is something I noticed:
If you have a non-prime number z in the answer, it can be written as z = x*y where at least one of x or y is prime. I don't have a proof for this next part but it seems apparent (by example) that x+y is always less than or equal to x*y. This means using a non-prime number is never "efficient" in terms of picking numbers for your set, and is often inefficient.
Might edit later with more stuff I notice while waiting for experiments to run at work :D
I completely agree. I think that is why 2*2*3^332 looks so good since it combines what you stated, and what ndie.jokes was saying about how 2^500 just looks smart.
|
On September 03 2011 02:09 FetusFondler wrote:
Do you by any chance know quotient groups? I'm so confused about it... hahaha
Message me on Skype or PM me, or write an example in the thread!
|
On September 03 2011 01:52 Trezeguet wrote:Show nested quote +On September 03 2011 01:36 n.DieJokes wrote:
I'm trying to find a string of positive integers that sum to 1000 and and who's product is as high as possible. I'm not sure how to approach it, my instinct is to say 2^500 is the answer but I'm pretty sure thats wrong. I simplified it to 10 and the answer is 2+2+3+3. I'm 99% sure it'll have to be a string of primes for sort of obvious reason that would be wordy for me to write out. I've been playing around with these two equations, x=p1^n1*p2^n2....pk^nJ where p is a prime and n is its power and p1(n1)+p2(n2)+...+pk(nj)=1000 where I limit the primes I use somewhat arbitrarily. If I could narrow it down to 2 and 3 or something like that I could optimize and be done... Oh well, hope some of that makes sense. Thanks for doing this
I don't want the answer but if you have a hint or idea I'd like to see it. Ok, so I don't know the answer so I'm kind of typing out loud here, but to me 2^500 looks really good To me, it might be easier to solve it for 10, or 100 as the sum, and then look at how that will relate to 1000. So for 10: the possible integers are 1,2,3,4,5,6,7,8,9 and 10. Since we are trying to maximize the product, it is easy to say that 1 should be eliminated since that will not increase the product. Also, a simple answer is 4,6 and the product would be 24 so we know that a string of just "10" is wrong so we can eliminate that as well, also we know that 9 should not be used since the only combo is 1,9 which multiplies to 9. So this leaves us 2,3,4,5,6,7,8. Possibilities for 7 and 8 are 8,1,1 and 8,2 which (max = 16) doesn't beat 4,6 7,1,1,1 and 7,1,2 Max=(14) so 7 and 8 are out 6,1,1,1,1 = 6 6,1,1,2 = 12 6,1,3 = 18 6,2,2 = 24 6,4 = 24 5,2,2,1 = 20 5,3,2 = 30 5,4,1 = 20 5,5 = 20 ok, so it's looking like more, smaller numbers tends to be better 4,2,2,2 = 32 4,4,2 = 32 4,3,3 = 36 even better 3,2,2,2,1 = 24 3,3,3,1 = 27 3,3,2,2 = 36 just as good 2,2,2,2,2 = 32 So looking at this, it makes me thing that perhaps the best answer isn't 2^500, but it is probably very close. TLDR 2*2*(3^332) > 1*3^333 > 2^500 I just looked at 5^200 and (2^3)*(7^142) and it wasn't better. Also, obviously, using 4 and 2 are the same, but 2^3 > 8 and 2^4 > 16 so just use 2^x if you have extra bits left.
I have a proof for this if you want it later,
But the answer is:
[1000/(1000/e)] ^ {1000/e} where e ~ 2.71
|
Using Wolfram Alpha and only 2.71 as the approximation of e, I calculated it to be: 5.85148 X 10^159
|
On September 03 2011 02:20 IntoTheheart wrote:Show nested quote +On September 03 2011 01:52 Trezeguet wrote:On September 03 2011 01:36 n.DieJokes wrote:
I'm trying to find a string of positive integers that sum to 1000 and and who's product is as high as possible. I'm not sure how to approach it, my instinct is to say 2^500 is the answer but I'm pretty sure thats wrong. I simplified it to 10 and the answer is 2+2+3+3. I'm 99% sure it'll have to be a string of primes for sort of obvious reason that would be wordy for me to write out. I've been playing around with these two equations, x=p1^n1*p2^n2....pk^nJ where p is a prime and n is its power and p1(n1)+p2(n2)+...+pk(nj)=1000 where I limit the primes I use somewhat arbitrarily. If I could narrow it down to 2 and 3 or something like that I could optimize and be done... Oh well, hope some of that makes sense. Thanks for doing this
I don't want the answer but if you have a hint or idea I'd like to see it. Ok, so I don't know the answer so I'm kind of typing out loud here, but to me 2^500 looks really good To me, it might be easier to solve it for 10, or 100 as the sum, and then look at how that will relate to 1000. So for 10: the possible integers are 1,2,3,4,5,6,7,8,9 and 10. Since we are trying to maximize the product, it is easy to say that 1 should be eliminated since that will not increase the product. Also, a simple answer is 4,6 and the product would be 24 so we know that a string of just "10" is wrong so we can eliminate that as well, also we know that 9 should not be used since the only combo is 1,9 which multiplies to 9. So this leaves us 2,3,4,5,6,7,8. Possibilities for 7 and 8 are 8,1,1 and 8,2 which (max = 16) doesn't beat 4,6 7,1,1,1 and 7,1,2 Max=(14) so 7 and 8 are out 6,1,1,1,1 = 6 6,1,1,2 = 12 6,1,3 = 18 6,2,2 = 24 6,4 = 24 5,2,2,1 = 20 5,3,2 = 30 5,4,1 = 20 5,5 = 20 ok, so it's looking like more, smaller numbers tends to be better 4,2,2,2 = 32 4,4,2 = 32 4,3,3 = 36 even better 3,2,2,2,1 = 24 3,3,3,1 = 27 3,3,2,2 = 36 just as good 2,2,2,2,2 = 32 So looking at this, it makes me thing that perhaps the best answer isn't 2^500, but it is probably very close. TLDR 2*2*(3^332) > 1*3^333 > 2^500 I just looked at 5^200 and (2^3)*(7^142) and it wasn't better. Also, obviously, using 4 and 2 are the same, but 2^3 > 8 and 2^4 > 16 so just use 2^x if you have extra bits left. I have a proof for this if you want it later, But the answer is: [1000/(1000/e)] ^ {1000/e} where e ~ 2.71
I must be missing something so I could use some help, but
1000/(1000/e) is the same as (1000/1)* (e/1000) which = e and e is not an integer?
Also, 1000/e isn't a whole number so this will not result in a string of integers that sums 1000
|
On September 03 2011 02:25 Trezeguet wrote:Show nested quote +On September 03 2011 02:20 IntoTheheart wrote:On September 03 2011 01:52 Trezeguet wrote:On September 03 2011 01:36 n.DieJokes wrote:
I'm trying to find a string of positive integers that sum to 1000 and and who's product is as high as possible. I'm not sure how to approach it, my instinct is to say 2^500 is the answer but I'm pretty sure thats wrong. I simplified it to 10 and the answer is 2+2+3+3. I'm 99% sure it'll have to be a string of primes for sort of obvious reason that would be wordy for me to write out. I've been playing around with these two equations, x=p1^n1*p2^n2....pk^nJ where p is a prime and n is its power and p1(n1)+p2(n2)+...+pk(nj)=1000 where I limit the primes I use somewhat arbitrarily. If I could narrow it down to 2 and 3 or something like that I could optimize and be done... Oh well, hope some of that makes sense. Thanks for doing this
I don't want the answer but if you have a hint or idea I'd like to see it. Ok, so I don't know the answer so I'm kind of typing out loud here, but to me 2^500 looks really good To me, it might be easier to solve it for 10, or 100 as the sum, and then look at how that will relate to 1000. So for 10: the possible integers are 1,2,3,4,5,6,7,8,9 and 10. Since we are trying to maximize the product, it is easy to say that 1 should be eliminated since that will not increase the product. Also, a simple answer is 4,6 and the product would be 24 so we know that a string of just "10" is wrong so we can eliminate that as well, also we know that 9 should not be used since the only combo is 1,9 which multiplies to 9. So this leaves us 2,3,4,5,6,7,8. Possibilities for 7 and 8 are 8,1,1 and 8,2 which (max = 16) doesn't beat 4,6 7,1,1,1 and 7,1,2 Max=(14) so 7 and 8 are out 6,1,1,1,1 = 6 6,1,1,2 = 12 6,1,3 = 18 6,2,2 = 24 6,4 = 24 5,2,2,1 = 20 5,3,2 = 30 5,4,1 = 20 5,5 = 20 ok, so it's looking like more, smaller numbers tends to be better 4,2,2,2 = 32 4,4,2 = 32 4,3,3 = 36 even better 3,2,2,2,1 = 24 3,3,3,1 = 27 3,3,2,2 = 36 just as good 2,2,2,2,2 = 32 So looking at this, it makes me thing that perhaps the best answer isn't 2^500, but it is probably very close. TLDR 2*2*(3^332) > 1*3^333 > 2^500 I just looked at 5^200 and (2^3)*(7^142) and it wasn't better. Also, obviously, using 4 and 2 are the same, but 2^3 > 8 and 2^4 > 16 so just use 2^x if you have extra bits left. I have a proof for this if you want it later, But the answer is: [1000/(1000/e)] ^ {1000/e} where e ~ 2.71 I must be missing something so I could use some help, but 1000/(1000/e) is the same as (1000/1)* (e/1000) which = e and e is not an integer? Also, 1000/e isn't a whole number so this will not result in a string of integers that sums 1000
Damn, I forgot that they had to be integers. Whoops. T_T
Also e is Euler's constant.
Edit: FML just ignore the second line.
|
United States10328 Posts
+ Show Spoiler [motivation, or: why 1000/e] +Say you have a_1 + ... + a_n = 1000. Then by AM-GM (or lagrange multipliers, whatever), their product is maximized when a_1 = a_2 = ... = a_n (and is increased whenever you bring two variables closer together).
Furthermore, AM-GM says (a_1a_2...a_n)^{1/n} <= (a_1+a_2+...+a_n)/n = 1000/n, so a_1a_2...a_n <= (1000/n)^n. (The real value will be strictly less than (1000/n)^n if 1000/n isn't an integer.)
So now we want to find dY/dn, where Y = (1000/n)^n. Well log Y = n ( log 1000 - log n), so differentiating both sides w.r.t n, Y'/Y = log 1000 - (log n + 1), so Y' = (1000/n)^n * (log 1000 - log n - 1), which is 0 when (since (1000/n)^n is never 0)
log 1000 = log n + 1, or 1000 = e*n, or n = 1000/e ~= 367.8.
So this would give the maximum if they don't all have to be integers (set everyone equal to 1000/368 or 1000/367, whichever gives the bigger result). But notice 2 < 1000/368 < 3, so on to the real result...
We want to show every number in the product is either 2 or 3.
Say there's a number a >= 4 in the product. We claim that replacing a by (floor(a/2), ceil(a/2)) does not decrease the product (and if a > 4, it increases the product). Well, if a is even, then we're replacing a by (a/2, a/2) with product a^2/4... but a^2/4 >= 4*a/4 = a as desired. If a is odd, we're replacing a by ( (a-1)/2, (a+1)/2 ) with product (a^2-1)/4; but
(a^2-1)/4 >= a <==> a^2-4a-1 >= 0.
But a^2-4a-1 = 0 has larger root [by the quadratic formula] (4+sqrt(20))/2 = 2+sqrt(5) < 5, so a^2-4a-1 > 0 for a >= 5, which is equivalent to (a^2-1)/4 > a for a>=5, as desired.
Call the operation where we replace a by ( floor(a/2), ceil(a/2) ) a "split." It's obvious that splitting 2 or 3 into (1,1) and (1,2) respectively decreases the product, so we never want to split a 2 or a 3; but splitting any larger number increases the product (or in the case of 4, keeps the product the same, so we do that anyway.)
Now we want to show that a set of integers with sum S >= 2 has maximal product only if all the integers are 2 or 3 or 4.
Assume otherwise: we have a set with sum S >= 2, and maximal product. There can't be a 1 in the final set of integers because our algorithm doesn't allow it. If there's an integer >= 5, split it; we get a bigger product. Contradiction. So all the numbers in the set are 2, 3, or 4.
Split all the 4's into two 2's. Now all the numbers in the set are 2's or 3's.
Ok, now it's easy. Start with 2^500. We can increase the product by replacing (2,2,2) by (3,3) since 8 < 9. So, replace as many triples of 2's by pairs of 3's as possible; we get 2^2 * 3^(332) is the maximum, as desired. [And it's easy to check that we've actually gone over all sets with sum 1000 and only containing 2's and 3's].
On September 03 2011 02:09 whistle wrote:
Don't really have an answer and I'm not too good at math riddles, but I'm pretty sure your hunch about primes is correct:
If you have a non-prime number z in the answer, it can be written as z = x*y where at least one of x or y is prime. I don't have a proof for this next part but it seems apparent (by example) that x+y is always less than or equal to x*y. This means using a non-prime number is never "efficient" in terms of picking numbers for your set, and is often inefficient.
Might edit later with more stuff I notice while waiting for experiments to run at work :D
Well, xy >= x+y is equivalent to xy - x - y + 1 >= 1, which is equivalent to (x-1)(y-1) >= 1. So if both divisors x,y are greater than 1 (aka greater than or equal to 2), we have xy >= x+y.
I really wish TL had LaTeX capabilities LOL
|
Thank you for the great explanation!
|
On September 03 2011 02:13 Trezeguet wrote:Show nested quote +On September 03 2011 02:09 FetusFondler wrote:
Do you by any chance know quotient groups? I'm so confused about it... hahaha Message me on Skype or PM me, or write an example in the thread!
Ok, here's a question in my book I'm having a bit of trouble with:
Let G be a finite group, and let n be a divisor of |G|. Show that if H is the only subgroup of G of order n, then H must be normal in G
|
On September 03 2011 02:26 ]343[ wrote:
I really wish TL had LaTeX capabilities LOL
If we had that, would that make you happier as a writer for TL or sad? I mean if we had LaTeX half the forums would be about math and science and the rest would be in eSports.  (I'm just making the figures up but I'd come here to discuss math/physics since the rest of the internet's somewhere else)
|
United States10328 Posts
On September 03 2011 02:34 FetusFondler wrote:Show nested quote +On September 03 2011 02:13 Trezeguet wrote:On September 03 2011 02:09 FetusFondler wrote:
Do you by any chance know quotient groups? I'm so confused about it... hahaha Message me on Skype or PM me, or write an example in the thread! Ok, here's a question in my book I'm having a bit of trouble with: Let G be a finite group, and let n be a divisor of |G|. Show that if H is the only subgroup of G of order n, then H must be normal in G
Well, for H to be normal in G, we just need gHg^{-1} = H for all g in G. We already know gHg^{-1} is a subgroup of G (easy to check; it's a conjugate subgroup of H), and gHg^{-1} has the same order as H (since gh_1g^{-1} = gh_2g^{-2} <===> h_1 = h_2). So gHg^{-1} is a subgroup of G of order n... but since H is the only such subgroup of G, gHg^{-1} = H. And this is true for all g in G, so we're done
On September 03 2011 02:47 IntoTheheart wrote:Show nested quote +On September 03 2011 02:26 ]343[ wrote:
I really wish TL had LaTeX capabilities LOL
If we had that, would that make you happier as a writer for TL or sad? I mean if we had LaTeX half the forums would be about math and science and the rest would be in eSports. (I'm just making the figures up but I'd come here to discuss math/physics since the rest of the internet's somewhere else)
Personally I'd be happy, since I'm a bit tired of going to Art of Problem Solving and dealing with middle schoolers... lolol. (I think that just means I should be participating in the "real math" forums now instead of "AMC" and whatever... still stuck in the high school mindset  )
|
Well I was going to edit my post with new thoughts but that didn't seem to make sense in a thread like this one.
WTS that 2^2*3^332 is correct: one way is to show that we only want prime numbers and that prime numbers larger and smaller than 3 are inefficient.
+ Show Spoiler [attempted proof] +1. Show that using 3 should be prioritized over using 2. Consider the set A = {3,3} and the set B = {2,2,2} - they both have the same sum which means they are equivalent sets in terms of this problem. 3*3 = 9 and 2*2*2 = 8, meaning we never want to use set B when we can use set A (i.e. when the remaining sum that we want to fill is six or greater).
2. Show that using 3 should be prioritized over using all larger primes x. Compare {x-3,3} to {x} since they have the same sum and find the value of x where the two sets are equivalent...
(x-3)*3 = x
3x-9 = x
2x = 9
x = 4.5
f(x) = (x-3)*3-x is a monotonic function, and testing x = 5 shows (x-3)*3 > 5. This means including {x} is only efficient if x < 4.5, but there are no primes larger than 3 and less than 4.5.
Therefore, including 3 should be prioritized over all other numbers. The maximum number of 3 that can be added is 332, which leaves a remainder of 4 to be filled by 2*2. The final set is {3,3,...,3,2,2}.
I'm positive there's a cleaner way of doing the proof (if mine is even correct) but whatever!
IntoTheHeart - I'm interested in the proof for e! Won't be doing math ever again but finding out how things work is always cool 
EDIT: looks like 343 beat me with a proof that looks much more elegant... oh well! anyone want to see if mine is correct?
|
Holy crap 343, you're the bestest, the bee's knees... the cat's pajamas!!
But I'm having so much trouble with group theory in general, I honestly feel like I'm just pushing around letters and not learning anything... :\
|
United States10328 Posts
On September 03 2011 02:53 FetusFondler wrote:
Holy crap 343, you're the bestest, the bee's knees... the cat's pajamas!!
But I'm having so much trouble with group theory in general, I honestly feel like I'm just pushing around letters and not learning anything... :\
LOL me too actually. I just remember hearing something about conjugate subgroups... lololol. I didn't learn algebra very well... so I've been (pretending?) to do a few problems this summer. Hasn't been very effective...
|
United States10328 Posts
On September 03 2011 02:52 whistle wrote:Well I was going to edit my post with new thoughts but that didn't seem to make sense in a thread like this one. WTS that 2^2*3^332 is correct: one way is to show that we only want prime numbers and that prime numbers larger and smaller than 3 are inefficient. + Show Spoiler [attempted proof] +1. Show that using 3 should be prioritized over using 2. Consider the set A = {3,3} and the set B = {2,2,2} - they both have the same sum which means they are equivalent sets in terms of this problem. 3*3 = 9 and 2*2*2 = 8, meaning we never want to use set B when we can use set A (i.e. when the remaining sum that we want to fill is six or greater).
2. Show that using 3 should be prioritized over using all larger primes x. Compare {x-3,3} to {x} since they have the same sum and find the value of x where the two sets are equivalent...
(x-3)*3 = x
3x-9 = x
2x = 9
x = 4.5
f(x) = (x-3)*3-x is a monotonic function, and testing x = 5 shows (x-3)*3 > 5. This means including {x} is only efficient if x < 4.5, but there are no primes larger than 3 and less than 4.5.
Therefore, including 3 should be prioritized over all other numbers. The maximum number of 3 that can be added is 332, which leaves a remainder of 4 to be filled by 2*2. The final set is {3,3,...,3,2,2}. EDIT: looks like 343 beat me with a proof that looks much more elegant... oh well! anyone want to see if mine is correct?
So it looks like your algorithm is:
composite x*y [x, y > 1] --> (x, y, xy-x-y)
(2,2,2) --> (3,3)
p > 3 --> (3, p-3)
This looks fine, except one small thing: 6 --> (2, 3, 1) introduces a 1! How do you deal with that?
Ok sorry Trezeguet for hijacking your thread... I should go do some work now XD
|
Hijack away, this isn't about me, but about helping people so you are more than welcome!
|
On September 03 2011 03:03 ]343[ wrote:So it looks like your algorithm is:
composite x*y [x, y > 1] --> (x, y, xy-x-y)
(2,2,2) --> (3,3)
p > 3 --> (3, p-3)
This looks fine, except one small thing: 6 --> (2, 3, 1) introduces a 1! How do you deal with that?
If I had to make an algorithm I would take composite z (I had to look up composite hahahaha) and factor out any 3, then factor out 2... so 6 --> (3,3) instead of (2,[3,1]). I didn't try to make an algorithm, just show that 3 is the most "efficient" number to include in the set, so I might be misinterpreting your post...
This thread is making 5% of me consider taking more math classes...
|
United States10328 Posts
On September 03 2011 04:17 whistle wrote:
If I had to make an algorithm I would take composite z (I had to look up composite hahahaha) and factor out any 3, then factor out 2... so 6 --> (3,3) instead of (2,[3,1]). I didn't try to make an algorithm, just show that 3 is the most "efficient" number to include in the set, so I might be misinterpreting your post...
This thread is making 5% of me consider taking more math classes...
But factoring out a 3 from 6 leaves 2?
At least, from this
On September 03 2011 02:52 whistle wrote:
Well I was going to edit my post with new thoughts but that didn't seem to make sense in a thread like this one.
WTS that 2^2*3^332 is correct: one way is to show that we only want prime numbers and that prime numbers larger and smaller than 3 are inefficient.
and the previous post on x+y <= xy, it seems like you're trying to replace composite numbers by their factors, and "other stuff." Basically, I'm still not sure how you're justifying that "prime numbers are best." (You *could* just define a special rule for 6, lol.) [Really, I'm just nitpicking now... hehe.]
ALSO yes, take more math classes. Even if you don't want to take algebra or analysis, take some combinatorics (if your school has it)! Otherwise, maybe logic or algorithms (which is secretly not computer science). It's fun ^^
|
Well this is what I'm thinking:
Every composite number z can be written as a composite of primes x_i, and by your nifty proof, x_1*x_2*...*x_n >= x_1 + x_2 + ... + x_n. Thus including {z} in the set of answers contributes just as much to the end product as including {x_1,x_2,...,x_n}, but never "costs" less in terms of the sum of the terms of the subset. So if you were to include {z}, it would be better (or equivalent at least) to include {x_1,x_2,...,x_n} instead. If there is a composite number in the final set {y_i,...,z} with y_i all prime, it can always be re-written as a set with only prime members {y_i,...,x_i} without violating the total sum = 1000 rule while maintaining the same product.
Then I think the idea that 3 is the "best" prime number to use -- assuming we're now limited to primes -- holds? So the set can be further optimized.
Anyways I think the 6 problem may be solved by the constraint of sum = 1000, since you could have a set like {6,3,...,3,2,2} - 330 3s. Factoring would give {3,2,1,3,...,3,2,2} then you can combine one 2 and one 1 into a 3.
Regardless I don't think my proof is the right way to do it, you might call it nitpicking but I call it exposing a piecemeal shoddy proof . I mean thinking about primes makes sense logically but when I put it in writing it isn't very rigorous or convincing. I think I wrote this response mostly for myself to see whether I could convince myself that my proof is correct (and I failed) so you don't need to waste time picking it apart and responding haha
I took analysis last year and did very well but as the year went on I realized I totally hate proofs. It felt like most were just variations on a theme and it got a bit mundane (not easy, yes mundane) to figure out what the new trick was... I also realized I don't care how 99% of the proofs in math class are done it's all just very pointless to me. The topics-style classes sound pretty cool though so I'll probably take some!
|
United States10328 Posts
Oh, I think you're just overlooking something silly: you can't really replace z by {x_1, ... , x_n} because z != x_1 + x_2 + ... + x_n (you want to always preserve the sum!) But I think your proof works with a little tweaking.
Also, it seems like real analysis is just dry like that (I took algebra first, so I haven't actually taken real analysis yet... but from my friend's problem sets, it looks sort of... yeah, dry.) Math gets more interesting, I promise  Try some Putnam problems (they're mostly interesting). Though it's true, as you get into higher math, "proofs" start to look more and more abstract, and you just start leaning on theorems and definitions you already know... look for the intuition behind the proof!
|
|
|
|
|
|
EPT
