Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?

share|cite|improve this question
up vote 0 down vote accepted

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).

share|cite|improve this answer
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.

share|cite|improve this answer
can you give a short explanation why? – Glougloubarbaki Nov 23 '11 at 22:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.