Hey I am having trouble with this problem



I get that the answer is with 3's and 2's (in particular only one 2 and the rest are 3) but I cannot find a proof of why. In class we made a remark for the number 5 and 6:

If the sum adds up to 5 we have 4+1, 2+2+1, 3+2, etc. We notice that the largest product is from 3 and 2.
If the sum adds up to 6, we have 3+3, 2+2+2. The largest product is from 3 and 3 and so if we have a choice of 3's or 2's, we go with 3's, hence the answer for 2015 consists of 671 3's and only one 2.

I can't find a proof of why this gives us the largest, can anyone help?

Perhaps induction on n > 5? For n > 5 we have that n = a+b and a*b > n? Something like this?

Thanks

First notice that :
5 = 2+3, with 2*3 > 5
6 = 3+3, with 3*3 > 6
7 = 4+3, with 4*3 > 7
and so on :
Every integer n > 4 can be written as a sum of terms, with a product > n.
A proof is easy if you consider (n/2) + (n/2) = n, when n is even : (n/2)² > n for every n > 4 ;
and (n+1)/2 + (n-1)/2 = n, when n is odd : (n² - 1)/4 > n for every n > 4 (true for every real x > 2 + √5.

In other words, you must never use any integer > 4 in your sum, because if you do so, you could always find a better one.

Using 4 is the same thing as using 2 and 2, since 2+2=4 and 2*2 = 4.

So we may assume that only 2's and 3's are used (obviously you won't use 1's).

As you already said, each time you can use 3's over 2's, you win, since for the same sum of 6, 3*3 > 2*2*2.
Hence your answer 671 3's and one 2 stands.

General pattern :
if n is a multiple of 3 : use only 3's,
if n = 1 [3], use 2 2's and then only 3's,
if n = 2 [3], use one 2 and the rest of 3's.

Is this just a result by checking 5, 6, and 7? Or is there a more formal way to show this is true?

You want to add up as small of numbers as possible because you have a summation limit not a multiplication limit.

For instance, 66! (or 66 factorial)
If you add up every number in that sequence you end up with 2211.
66! itself = 2.72172x10^92

If you do 64! and add up all of the numbers then you get 2080.
If you do 63! and add up all of the numbers then you get 2016.

But, since we want our product number to be large we do not use 1 because that would be a waste of a number.

So we do 63! and add up all of the numbers except 1 and get 2015, which is exactly what we wanted.

Our numbers are all of the numbers between and including 2 and 63, and when you multiply them all together your product is equal to 63! which would be 1.98260831540444x10^87

This post was edited by Dontrunaway on Oct 23 2015 04:50pm

that product is much smaller than the solution.
given all 3s and a single 2, the product is 2*3^671. for simplicity, we can lower the bound to simply 3^671 since if your product is smaller than this number, it must be smaller than the real product.
for simplicity, i will extend Your product similarly. product of 63! is smaller than 63^63 which is smaller than 81^63 or (3^4)^63 or 3^252. it's easy to see 3^252 < 3^671, so your answer is sub-optimal.

with that said, this isn't a bad starting place. the question is can you increase the product from your sequence?instead of the 8 in your sequence (+8 and *8), replace it with four 2s (+8, *16) and we see a larger product. we can see by splitting large numbers up, the sum will stay the same but the product goes up. so break it down as far as you can.

This post was edited by carteblanche on Oct 23 2015 05:39pm

Any integer > 4 has been checked, not only 5, 6, 7. See my previous post.

To prove it in a more formal way, suppose you have a given N ( N = 2015 in your example), and suppose N is the sum of a1, a2, ..., ap, with all ai integers :

N = a1 + a2 + ... + ap

Now assume that at least one of the ai equals something greater than 4. We may assume that we are talking about the last one : ap > 4.

If ap is even, you can also write : N = a1 + a2 + ... + a(p-1) + (ap/2) + (ap/2)
If ap is odd, you can write : N = a1 + a2 + ... + a(p-1) + ((ap+1)/2) + ((ap-1)/2)

Now compare the products :

P = a1*a2*...*ap (your original one)
Q = a1*a2*...*a(p-1)*(ap/2)*(ap/2), in case ap is even
Q = a1*a2*...*a(p-1)*((ap+1)/2)*((ap-1)/2), in case ap is odd.

Since ap > 4, Q > P as proven above.
And that proves that a decomposition of N using at least an integer > 4 can not give the largest possible product.

Thank you everyone! I should have the proof now

My solution assumed that no integers were duplicated, and since adding up 2->63 equals EXACTLY 2015, it was likely that it was the intended solution.

The prompt does not specifically state either way, so it is up for interpretation.

This post was edited by Dontrunaway on Oct 23 2015 07:42pm

It's not up for interpretation if it's not specified...

Use Lagrange Multipliers.
Bro.