woowheedr

Answered

2022-07-01

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}^{n}{x}_{i}=m$ and $\prod _{i=1}^{n}{x}_{i}$ is maximized, where $n$ and all ${x}_{i}$'s are integers. In particular, is the maximum product $\prod _{i}{x}_{i}$ polynomial in $m$?

Answer & Explanation

Karissa Macdonald

Expert

2022-07-02Added 12 answers

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

Crystal Wheeler

Expert

2022-07-03Added 4 answers

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}\ge 5$ 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.

EDIT: An explanation, as requested.

First show that if there's an i such that ${x}_{i}\ge 5$ 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.

Most Popular Questions