Suppose that we have a integer m, and we need to choose n ≤ m and x 1 , x 2 , . . . , x n such that ∑ i = 1 n x i = m and ∏ i = 1 n x i is maximized, where n and all x i 's are integers. In particular, is the maximum product ∏ i x i polynomial in m?

Question

Suppose that we have a integer   m, and we need to choose   n  ≤  m and       x    1    ,      x    2    ,  .  .  .  ,      x    n   such that       ∑          i      =      1        n        x    i    =  m and       ∏          i      =      1        n        x    i   is maximized, where   n and all       x    i  &#039;s are integers. In particular, is the maximum product       ∏    i        x    i   polynomial in   m?

Karissa Macdonald · Accepted Answer

Nope, since it is not even bounded by a polynomial : if   m is even, for example, you may take the decomposition       x    i    =  2 and   n  =  m      /    2 to obtain a product       2          m              /            2       wich exceeds polynomial growth (and I&#039;m not claiming this is the maximum, but it is a lower bound).

Crystal Wheeler · Accepted Answer

I think you&#039;ll find the product is maximized by using as many threes as possible, topping up with a two or two.EDIT: An explanation, as requested.First show that if there&#039;s an i such that       x    i    ≥  5 then you can increase the product by replacing       x    i   by two numbers that add up to       x    i  . Also, replacing 4 by two 2s doesn&#039;t change sum or product, so we may assume all       x    i   are 2 or 3. Now note that if you have three 2s you can do better with two 3s.