# Upper bound of the optimal value in one particular maximization problem

Suppose that we have a integer $m$, and we need to choose $n\le m$ and $x_1,x_2,...,x_n$ such that $\sum_{i=1}^nx_i=m$ and $\prod_{i=1}^nx_i$ is maximized, where $n$ and all $x_i$'s are integers. In particular, is the maximum product $\prod_ix_i$ polynomial in $m$?

-

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'm not claiming this is the maximum, but it is a lower bound).

-
Thanks, that's so obvious, how did I not think of that... – sxu Nov 23 '11 at 22:02
happens to everyone ;) – Glougloubarbaki Nov 23 '11 at 22:12

I think you'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's an $i$ such that $x_i\ge5$ 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'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.

-
can you give a short explanation why? – Glougloubarbaki Nov 23 '11 at 22:04