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.