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$?
Upper bound of the optimal value in one particular maximization problem
0
$\begingroup$
combinatorics
optimization
2 Answers
0
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).
-
0happens to everyone ;) – 2011-11-23
2
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.
-
0can you give a short explanation why? – 2011-11-23