Problem Solving :))))

problem solving:

Products of sums

Understand the problem:  To find the positive integers that have the biggest product and sum is n.

Devise a plan: start from the small numbers and try to find what kind of numbers will give the maximum product.

Carry out:

n             integers sum to n                                                                             max product 

1                1                                                                                                              1(1)

2                (1,1)                                                                                                        1(1,1) 

                             

3                (1,1,1), (1,2),(3)                                                                                       3(3)  

                      

4                (1,1,1,1),(1,1,2),(2,2)(3,1),(4)                                                              4(2,2)   

                               

5                (1,1,1,1,1),(1,1,1,2)(1,1,3),(2,2,1),(2,3)(5)                                            6(2,3)     

                         

6                (1,1,1,1,1,1),(1,1,1,1,2),(1,1,2,2),(1,1,1,3),                                            9(3.3)

                  (1,1,4),(1,2,3),(2,2,2),(2,4),(3,3),(6)   

7                …                                                                                                   12(3,2,2)

8                …                                                                                                    18(3,3,2)

9                …                                                                                                       27(3,3,3)

.

.

.

n

All the products have the factor 2 and 3 except the first 2. Actually there are more factor 3 than factor 2. After I did some work on the paper, i found when we want the max product, the most number of factor 2 is 2 and the other factor are all 3.

Also all the sums that include 1 cannot be the max product. Because n > 1(n-1)

So in my opinion, the positive integer n the maximum product will contain the factor 2 and 3

but I found there are many cases in this problem.

The first one: n is a perfect square number(such as 16, 25…)

                        in this case the max product is n^(sqrt(n))

The second one: n % 3 = 0 (such as 6,9,12):

                                in this case the max product is 3^(n/3)

The third one: n % 3 = 1 (such as 10, 13…)

                          in this case first spilt n to two positive integer, the first one can be        

                          divided by 3, the  second

                          one can be divided by 2. Let the first one as larger as possible.

                          in order to do this. 

                          let s = n // 3 then max product is (3^(s-1))*(2 * 2)

                          because when n % 3 has the remainder 1, that shows when we want  

                          the most number of factor 3, there is a factor 1 

                          remain, in order to make the product max, let one factor 3 be 2 and  

                          let this 1 be 2   #(1*3<2*2)

The fourth one n % 3 = 2 (such as 14, 17,20…)

                         in this case is very similar to the third one.

                         still let s = n // 3 then the max product is (3^s)*2

                          because in this time we don't have 1 left when we want the most    

                          number of 3 as the factor. 

I do not think there has other case, because when a positive integer divided by 3 the only possible remainders are 0,1,2. 

That was all of my proof. Maybe there had some problem. Because I didn't actually calculator after n > 15, that is a huge work. But I compared the product that I got by using my formula with the number different from I got. The formula actually gave the numbers that have the maximum product.