Maximizing product of three integers

405 Views Asked by At

It is well-known that, if we want to partition a positive number $m$ into a sum of two numbers such that their product is maximum, then the optimal partition is $m/2, ~ m/2$. If the parts must be integers, then the optimal partition is $\lfloor m/2 \rfloor, ~\lceil m/2 \rceil$.

This can be generalized to weighted product. Suppose $w_1,w_2$ are fixed weights with $w_1+w_2=1$. Consider the following maximization problem:

$$ \text{maximize} ~~~ m_1^{w_1}\cdot m_2^{w_2} \\ \text{subject to} ~~~ m_1+m_2 = m $$

By taking derivatives one can find that the optimal partition is $w_1 m,~w_2 m$; and if the parts must be integers, then the optimal partition is either $\lfloor w_1 m\rfloor,~\lceil w_2 m\rceil$ or vice-versa $\lceil w_1 m\rceil,~\lfloor w_2 m\rfloor$; in particular, for each $i\in\{1,2\}$, $m_i \leq \lceil w_i m\rceil$.

My question is: does this result extend to $3$ parts? That is: in the following optimization problem (where the sum of weights is $1$):

$$ \text{maximize} ~~~ m_1^{w_1}\cdot m_2^{w_2}\cdot m_3^{w_3} \\ \text{subject to} ~~~ m_1+m_2+m_3 = m $$ Is it always true that, when all $m_i$ must be integers, then $m_i \leq \lceil w_i m\rceil$ for each $i\in\{1,2,3\}$?

2

There are 2 best solutions below

1
On BEST ANSWER

The answer to your question is YES. Because the problem is fully symmetric in the indices, it suffices to show for example that $m_3 \leq \lceil w_3 m \rceil$. Since the maximum value is positive, we see that none of the $m_i$ is zero, so each $m_i$ is $\geq 1$. If $m_3=1$ we are done, so we may assume that $m_3\geq 2$.

Let $f(x,y,z)=x^{w_1}y^{w_2}z^{w_3}$. Because $(m_1,m_2,m_3)$ is optimal, we have $f(m_1,m_2,m_3) \geq f(m_1+1,m_2,m_3-1)$, or

$$ w_1 \leq w_3\frac{\log\big(\frac{m_3}{m_3-1}\big)}{\log\big(\frac{m_1+1}{m_1}\big)} \tag{1} $$

Similarly, from $f(m_1,m_2,m_3) \geq f(m_1,m_2+1,m_3-1)$ we deduce

$$ w_2 \leq w_3\frac{\log\big(\frac{m_3}{m_3-1}\big)}{\log\big(\frac{m_2+1}{m_2}\big)} \tag{2} $$

Adding up those two equations and remembering that $w_1+w_2+w_3=1$, we see that $w_3 \geq W$ where

$$ W=\frac{1}{1+\frac{\log\big(\frac{m_3}{m_3-1}\big)}{\log\big(\frac{m_1+1}{m_1}\big)}+\frac{\log\big(\frac{m_3}{m_3-1}\big)}{\log\big(\frac{m_2+1}{m_2}\big)}} \tag{3} $$

Since $m_3 \leq \lceil w_3 m \rceil$ follows from $m_3-1 \lt w_3m$, it suffices to show that $W_2\gt 0$ where

$$ W_2 = W - \frac{m_3-1}{m} = \frac{1}{1+\frac{\log\big(\frac{m_3}{m_3-1}\big)}{\log\big(\frac{m_1+1}{m_1}\big)}+\frac{\log\big(\frac{m_3}{m_3-1}\big)}{\log\big(\frac{m_2+1}{m_2}\big)}} - \frac{m_3-1}{m_1+m_2+m_3} \tag{4} $$

Let us now proceed with the proof of the positivity of $W_2$. It is convient to make the change of variables $x=\frac{m_3}{m_3-1}$ ; then $m_3=\frac{x}{x-1}$, and the range of $x$ is $(1,2]$. Also $W_2$ can be rewritten as

$$ W_2= \frac{1}{1+\frac{\log(x)}{\log\big(\frac{m_1+1}{m_1}\big)}+\frac{\log(x)}{\log\big(\frac{m_2+1}{m_2}\big)}} - \frac{1}{(m_1+m_2+1)x-(m_1+m_2)} \tag{5} $$

So that $W_2 \gt 0$ iff $W_3 \gt 0$, where

$$ W_3=(m_1+m_2+1)(x-1)-\frac{\log(x)}{\log\big(\frac{m_1+1}{m_1}\big)} -\frac{\log(x)}{\log\big(\frac{m_2+1}{m_2}\big)} \tag{6} $$

Now, $W_3=(x-1)(H(m_1,x)+H(m_2,x)+1)$ where

$$ H(t,x)=t-\frac{\frac{\log(x)}{x-1}}{\log\big(\frac{t+1}{t}\big)} \geq t-\frac{1}{\log\big(\frac{t+1}{t}\big)} \tag{7} $$

We deduce that $W_3 \geq (x-1)(I(m_1)+I(m_2)+1)$ where $I(m_i)=m_i-\frac{1}{\log\big(\frac{m_i+1}{m_i}\big)}$. Let $t\in\lbrace m_1,m_2 \rbrace$ minimize $I(t)$, so that $I(m_1)+I(m_2)\geq 2I(t)$. It therefore suffices to show that $W_4 \gt 0$ where

$$ W_4=2\Bigg(t-\frac{1}{\log\big(\frac{t+1}{t}\big)}\Bigg)+1\tag{8} $$

This amounts to $2t+1\gt \frac{2}{\log(1+\frac{1}{t})} $, or $K(t)\gt 0$ where

$$ K(t)=\log\bigg(1+\frac{1}{t}\bigg)-\frac{2}{2t+1} \tag{9} $$

Now,

$$ K'(t)=-\frac{1}{t(t+1)}+\frac{1}{(t+\frac{1}{2})^2}= -\frac{1}{t(t+1)(2t+1)^2} \lt 0. \tag{10} $$

So $K$ is decreasing on $[1,\infty)$, and hence $K(t)\geq \lim_{\infty}(K)=0$. This finishes the proof.

1
On

This example seems to fail for $w_i=1/3$ for $i=1,2,3.$ Let $m:=2^{10}+1=1025$ and note that the maximum cost is achieved for $m_1=m_2=341$ and $m_3=343.$ However the constraint you desire gives $$m_i \leq \lceil m/3 \rceil=342.$$

Note: If you use the log-sum inequality you can look at maximizing the log of your cost function (LHS below) $$ \sum_{i=1}^3 w_i \log m_i \geq \log m $$ but I believe it's the floor/ceiling constraints that will defeat you, but it's too late in the day for me right now to continue.