## MMM #15: We have a winner!

Richard Berlin, who has been participating in Monday Math Madness! for quite a while, was picked as the winner for this contest by Random.org. Congratulations, Richard! I'll be sending you your prize so send me your address. Stand by for another Monday Math Madness on Monday at Blinkdagger.

Here is Richard's solution:

Find a set of positive integers which add up to 2008 and which yield the largest product. What is the prime factorization of this largest product?

Let's experiment with some small numbers.

The first nontrivial one is five. The choices for sets that sum to 5 are {1,4} or {2,3} Clearly the latter is preferable; our set should never contain ones, because they don't increase the product.

Let's try a slightly larger number, say, 8. The sets with 2 members--excluding ones--are {2,6} {3,5} {4,4} In this case, 4,4 gives the largest product. But can we do better with sets that have more members? With three members, we can have {2,3,3} and {2,4,2}. You can see that these two sets can be derived from the ones with fewer members by replacing the largest member with two smaller ones, i.e. {2,6} becomes {2,3,3} but has a larger product. {3,5} also yields {2,3,3}. {4,4} cannot be improved upon because a substitution would replace a 4 with {1,3} or {2,2} which is either a loss or a wash. But converting a five to {2,3} and converting a six to {3,3} will both increase our product.

We therefore wish to have a sum which contains no ones, 1 or 2 twos, and as many threes as possible.

The set which satisfies these properties contains 668 threes and 2 twos. (668*3 + 2*2) = 2008.

The product is therefore (3**668)*2*2. This is a very large number indeed, roughly 2.08477 x 10^319:

2084769976861585425784485312862381843383604649028790868

2525210460004940394794697844313846774093197186310085664

6401808632334506601836564979910436831329986734532785642

5484166418298557355250048052076718997217799369283566656

5481977395020427128499296468195198604805753326271637173

206954379232852022401310622811561644294735044

Guy Srinavasan made this interesting observation:

All other things being equal, you get the most log-product for your addend with the integer "3". ln(3)/3 > ln(n)/n for any other positive integer n. So we should expect the product to be somewhere around 3^(2008/3).

David Miles observed the following:

For any number n, the maximum product which can be obtained from a set of numbers adding to n is e^(n/e).

And, Chao Xu noticed something similar:

First notice that

a^2>=(b-m)(b+k)

where

2b-m+k = 2aThis give us a hint that the maximum product when sum is equal to n might be a^(n/a) or some simple variation.

Thanks for your participation. If you keep playing, your odds of winning will go up!

mborkOctober 8th, 2008 - 02:40

Well, I also solved this one (apart from factorizing it, I was too lazy…), but got *another* solution…

The point is, that formally, a *set* may contain each member only once.

So the problem I really solved was: represent 2008 as a sum of *pairwise different* positive integers such that their product is maximal.

Which is also an interesting problem – but not *very* difficult – I did it for any N, not necessarily 2008 – and it took about 2 hours;). What was a bit more difficult, it was a *formal* proof of its maximality.