Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

2 Answers 2

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|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|improve this answer
    
can you give a short explanation why? –  Glougloubarbaki Nov 23 '11 at 22:04

Your Answer

 
discard

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.