products of sums

products of sums

The list of positive integers that add up to 1 is (1), and the product of this list (if you allow unary products) is also 1.

There are two lists of positive integers that add up to 2, and they yield two different products: (2) (with product 2), and (1,1) (with product 1).

There are several lists of positive integers that add up to 3, and they yield several different products: (3) (with product 3), (2,1) (with product 2), and (1,1,1) (with product 1).

If n is a positive integer, what is the maximum product that can be formed of a list of positive integers that sum to n?

Solution:

My idea is to separate integers from the total sum. Each action of separation must be attribute to the product as much as possible. And also we have to make sure the integer left is helpful to increase the sum as much as possible.

So in this idea, no number ‘one’  will appear in this list because one product any number equals itself. In other words, ‘one’ is a waste of sum. let us discuss it further, if there is a integer ‘three’, the biggest product will be itself. If there is a ‘four’, choose to separate it as 2 * 2 will be bigger than  1 * 3. If there is a 5, it will be 2 * 3. And as for 6, 3 * 3 is the biggest. For 7, it will be 3 * 4  =  3 * 2 * 2. 

The rule is to get as much 3 as possible. But if separating the last three from the total sum leave a 1, the last 3 will not be separate, and will separate the last 4 integer together as 2 + 2. If separate the last three leave a 2, it will be fine because 2 * 3 is the biggest product of sum 5. 

Finlay, the common solution of this problem is: divide the sum by 3. Name the integer N.  And if the reminder is 1, the power N minus 1, and product equals 3^(N - 1) * 2 * 2. If the reminder is 2, product equals 3^N * 2.