Maximize the product of two integer variables with given sum

Question

Let's say we have a value $K$. I want to find the value where $A+B = K$ (all $A,B,K$ are integers) where $AB$ is the highest possible value.

I've found out that it's:

• $a = K/2$; $b = K/2$; when $K$ is even

• $a = (K-1)/2$; $b = ((K-1)/2)+1$; when $K$ is odd.

But is there a way to prove this?

Answer 1

In the even case, assuming $A\leq B$, the numbers will be of the form $A=\frac{K}{2}-m$ and $B=\frac{K}{2}+m$ in order to get $A+B=K$, with $m=0,1,\ldots,\frac{K}{2}$. Then multiplying gives $AB=\left(\frac{K}{2}\right)^2 - m^2 \leq \left(\frac{K}{2}\right)^2$.

In the odd case, you'll have $A=\frac{K}{2}-m-\frac{1}{2}$ and $B=\frac{K}{2}+m+\frac{1}{2}$, with $m=0,1,\ldots,\frac{K-1}{2}$. Multiplying gives

$\begin{align*} AB &= \left(\frac{K}{2}\right)^2 - \left(m+\frac{1}{2}\right)^2 = \frac{K^2}{4} - m^2 - m - \frac{1}{4} \\ & = \frac{K-1}{2}\left(\frac{K-1}{2}+1\right) - m^2 - m \leq \frac{K-1}{2}\left(\frac{K-1}{2}+1\right). \end{align*}$

Alternatively, you can think of optimizing a quadratic function by finding the vertex. If you write $AB$ as a quadratic function of $A$ or $B$ alone using the constraint $A+B=K$ (as indicated in PEV's answer), then the closest integer to the vertex will solve your problem because the parabola opens down.

Answer 2

We know that $B = K-A$. So you want to maximize $AB = A(K-A)$. So we have:

$$AB = A(K-A)$$

$$ = AK-A^2$$

Find the critical points and use some derivative tests.