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.

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

Sorry if i ask this question. probably it's already answered somewhere else but i didn't find it.

Suppose to have a natural number $n \ge 0$.

Given natural numbers $\alpha_1,\ldots,\alpha_k$ such that

  • $k\le n$
  • $\sum_i \alpha_i = n$

what is the maximum value that $\Pi_i \alpha_i$ could take?

I'm quite sure that there is a theorem telling me the result but i cannot find it. For sure an upper bound is $n^k$ but i'm searching for a real upper bound. I'm pretty sure that upper bound should be $n^2$ but i don't know i could prove it.

share|cite|improve this question
    
The upper bound is much bigger than $n^2$. Suppose $n$ is even. Then $n = 2+2+\cdots+2$, and the product is $2^{n/2}$. If $n$ is odd you can take $n = 2+2+\cdots+3$ and get $3\cdot2^{(n-1)/2}$. – MJD Mar 27 '12 at 14:04
    
If you partition $n$ into about $\sqrt n$ parts of size about $\sqrt n$, then the product is $n^{{1\over2}{\sqrt n}}$, which is pretty big, even bigger than $2^{n/2}$ for certain $n$. – MJD Mar 27 '12 at 14:17

Using the fact that for real $x$, the function $x(k-x)$ rises steadily to a maximum at $x=k/2$, and then falls, we can see that for a maximum no part can be $\ge 5$. (If $k \ge 5$, we can always do better by splitting as $a +(k-a)$, where $a$ is the nearest integer to $k/2$.)

Note also that the splitting $6=3+3$ gives a greater product than $6=2+2+2$, and that whether we split $4$ as $2+2$ or not doesn't matter. So without loss of generality we can assume $3$'s and $2$'s, and no more than two $2$'s.

Thus if $n$ is divisible by $3$, use all $3$'s. If $n \equiv 2 \pmod{3}$, use one $2$ and the rest $3$'s. If $n\equiv 1\pmod {3}$, and $n>1$, use two $2$'s (or one $4$) and the rest $3$'s.

share|cite|improve this answer

Since the maximum product of two positive integers with fixed sum occurs when the factors are as equal as possible, the same is true if there are more than two factors (consider equalizing two of the summands/factors to increase the product where possible).

If we simply wanted a realistic upper bound for fixed number $k$ of factors/summands, without the trouble of worrying over divisibility, then consider the real version of the problem and the maximum product $(n/k)^k$.

If we then want to choose integer $k \ge 1$ which maximizes that, we can look at the logarithm of the product for simplicity:

$$ k \ln(n/k) = k (\ln n - \ln k) $$

A little calculus shows this is a unimodal function with respect to $k$ whose peak occurs around $k = n/e $.

share|cite|improve this answer

Hardmath are you sure the peak of this function occurs around $k = n/e$?

I think it occurs around $k = \pi$, I guess this would also explain intuitively why André Nicolas reasoning works, I didn't prove it, but looks like he is taking integer parts in a such a way that the sum of the differences of each part with $pi$ is as smallest as possible.

share|cite|improve this answer
    
Please think adding a comment on Hardmath post instead of adding a separate answer, which is completely far from what the OP is asking. – Nizar Dec 7 '15 at 13:55
1  
I can't add a comment to his post because my account is new. It says I must have 50 reputation to comment. – Henrique Vieira Dec 7 '15 at 14:53

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.