Problem 3

What set of positive integers sums to 2005 and has the greatest possible product?

Note: the numbers do not have to be distinct.

Solution:  Let S be the desired set of numbers.  S can not have more than one 1, since any two 1's could be replaced with a 2 and the sum would still be 2005, while the product would increase.  For that matter, S can not even contain a single 1 since that 1 and any other number, say n, could be replaced with n+1, and again the sum would be unchanged while the product goes up.  On the other hand any number n greater than 3, could be replaced with n-2 and 2, and the product would again go up or at least stay the same (in the case of n=4).  Thus, we may assume that S only contains 2's and 3's.  Lastly, if there were more than two 2's in S, then we could replace three 2's with two 3's and the product would again go up.  So there are at most two 2's in S.  But by now we have forced S to only have one possibility - namely S has 667 3's and 2 2's.  Note, this is not the only S that works - recall from the above comment we could also pick S to have 667 3's and a single 4.