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:

equation

because

equation

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 3Sum S(N)Largest product P(N)
equationequationequation
equationequationequation
equationequationequation

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:

equation

equation

equation

and:

equation

equation

equation

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

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

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:

equation

and calculate the product of the terms:

equation

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

equation

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

If S=3k then:

IfThen
equationequation
equationequation
equationequation

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

If S=3k+1 then:

IfThen
equationequation
equationequation
equationequation

equation

The maximum is reached for any m< S.

If S=3k-1 then:

IfThen
equationequation
equationequation

equation
equationequation

equation

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

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