The user-friendly version of this content is available here.

The following content is copyright (c) 2009-2013 by Goods of the Mind, LLC.

This essential trains for: AMC-10, AIME, AMC-12, Math Kangaroo 9-10.

Question: Suppose we have a number of positive integers and we know their sum. What would be the largest possible product of these integers?

Note that the number of numbers is variable.

Down to earth informal proof for pedestrians: Notice that, if we split the sum into two terms, the terms multiply to a number larger than the sum provided none of the terms is equal to one.

Now take each term and split it further into two terms (each larger than one) recursively. At each split, the product is larger.

Eventually, we get to have only terms of 2 or 3. The product of these terms will look like the product of a power of 2 multiplied by a power of 3.

However, at this stage, notice that:

because

Therefore, we have to replace a group of three factors of 2 (if existing) by a group of two factors of 3. At the end of this process, no more than two factors of 2 can remain in the product. All the remaining factors are factors of 3.

The conclusion is that the largest product depends on the remainder we get when we divide the sum by 3:

Residue of S(N) mod 3 | Sum S(N) | Largest product P(N) |

Formal Proof using Induction:

Let us denote the largest product of a set of numbers that add up to S by P(S).

Experimenting with small sums, we obtain:

and:

Based on these observations we conjecture that the product depends on the sum in the following way:

Sum S(N) | Largest product P(N) | |

We can prove this conjecture using induction. The base case has already been verified for P(2), P(3), P(4), etc.

The product is largest if we select the way to split the sum into two terms such that the product is maximal:

and calculate the product of the terms:

The product we are looking for is the largest product we can get by varying m:

Assume the conjecture is true for all m such that 0< m< n

If S=3k then:

If | Then |

The maximum is reached for any m< S of the form m=3l.

If S=3k+1 then:

If | Then |

The maximum is reached for any m< S.

If S=3k-1 then:

If | Then |

The maximum is reached for any m< S of the form m=3l.

The maximum values obtained are the ones predicted by the conjecture.