Given $a + b + c = 20$, find $\max(ab + ac + bc)$

Question

Given that $a + b + c = 20$, what's the maximum possible value for $ab +ac + bc$?
$$\left(a, b, c \in \mathbb{N}\right)$$

I tried following this post, Evaluating max(ab+bc+ac), which lead to: $ab + bc + ac = 200 - (b - 10)^2 - (c - 10)^2 - bc$, but I couldn't get anywhere afterwards.

Manually trying different numbers lead me to $a = b = 7, c = 6$ with a max result of $133$, but I can't prove it. I assumed for the sum to be the maximum, $a, b, c$ have to be as big as possible, therefore they should be as close to $\frac{20}{3}$ as possible. But is that really the case? If so how can it be proven?

Answer 1

Here is a Solution :

$a+b+c=20$
$(a+b+c)^2=400$
$a^2+b^2+c^2+2(ab+bc+ca)=400$
$X=(ab+bc+ca)=200-(a^2+b^2+c^2)/2$

We want to maximize X which occurs when $Y=(a^2+b^2+c^2)$ is minimized.
When $a<b$ , we can increase $a$ by $\delta$ while decreasing $b$ by $\delta$ (keeping total sum Constant) , which decreases $Y$.

When $a>b$ , we can decrease $a$ by $\delta$ while increasing $b$ by $\delta$ (keeping total sum Constant) , which decreases $Y$.

Likewise , $b<c$ , $b>c$ , $c<a$ , $c>a$ can all be adjusted to "Equality" to minimize $Y$.
We can not adjust further when we have attained "Equality" for the 3 variables.

In other words , $Y$ is minimum when $a=b=c=20/3$
In that Case , $X=3(20/3)(20/3)=400/3=133.333$ is the maximum , when $a,b,c$ are real numbers. When these are Integers, this value is the upper bound.

We can take nearest Integers $(a,b,c)=(7,7,6)$ to get the Integral maximum $7\times7+7\times6+6\times7=133$.

Answer 2

Since it seems to be have been answered in the comments, here's an algorithmic approach: Keep one variable constant (say $b$).
$$\max(ab+bc+ac)$$ $$\max(b(a+c)+ac)$$ $a+c$ is constant since we have kept $b$ to be constant. Let $a+c = k$:
$$\max(bk+a(k-a))$$Thus, if one variable is kept constant, the maximum occurs when the other two are equal (or as close as possible).
Suppose you have an initial solution $a_0,b_0,c_0$ such that $a_0+b_0+c_0 = 20$ but $a_0b_0+b_0c_0+a_0c_0$ is not maximum. Replace both $a_0$ and $c_0$ by $a_0+c_0\over 2$ (if $a_0$ and $c_)$ have opposite parities, then replace $a_0$ by $a_0+c_0+1\over 2$and $c_0$ by $a_0+c_0-1\over 2$) and call them $a_1$ and $c_1$. Now do this process with $a_1$ and $b_0$, then with $b_1$ and $c_1$, then with $a_2$ and $c_2$ and so on.
The sum remains the same at each algorithm step, but $ab+bc+ac$ increases.

We know that after every step, the value must increase, however, there exists a maximum (since there are only finite possible values for $a,b,c$). Thus, when we reach the maximum, the algorithm will produce no new triplet (it may swap values).
Thus, the maximum will be such that there will be no natural number between any two variables (otherwise replace both of them by that number(s) and we get a more optimal solution)
It is easy to see that two variables must be odd and one even otherwise all even. If they are all even, then there exists a natural number between two of them, which is more optimal than the previous solution. Thus the maximal solution will be 2 odd numbers and one even. If the two odd numbers are not equal, then there exists a number between them, which makes the solution more optimal. Thus they are equal. If the even number is not adjacent to them, then there exists a number between them, which makes the solution more optimal.
Thus, the solution consists of $2$ equal odd numbers and an adjacent even number. Only $\color{green}{(7,7,6)}$ satisfies this.

Answer 3

Define two vectors on Euclidean $\mathbb{R}^3$ equipped with the standard Euclidean inner product:

$$\vec{v} = (a, b, c) $$ $$\vec{u} = (b, c, a) $$

Then the inner product of these two vectors is given by:

$$\langle \vec{v}, \vec{u} \rangle = |\vec{v}||\vec{u}|\cos{(\sphericalangle(\vec{u},\vec{v})}) = ab+bc+ca = ab+ac+bc$$

Where the last equality is simply due to rearrangement of the terms.

We begin by maximizing the inner product $\langle \vec{v}, \vec{u} \rangle$ over $\mathbb{R}$. Since the inner product is clearly maximized when $\cos(\sphericalangle(\vec{u},\vec{v})) = 1$, we have:

$$ \max{\langle \vec{v}, \vec{u} \rangle} = |\vec{v}||\vec{u}|$$

Which in components reads:

$$ \max{\langle \vec{v}, \vec{u} \rangle} = ab+bc+ca = \sqrt{a^2+b^2+c^2}\sqrt{b^2+c^2+a^2}=a^2+b^2+c^2$$ $$ab+bc+ca=a^2+b^2+c^2$$

Now, the above maximizes $ab+bc+ca$ over $\mathbb{R}$, but since we want to maximize it over $\mathbb{N}$ we must find the actual maximal value in $\mathbb{R}$ to later derive the maximal value in $\mathbb{N}$. We add $2(ab+bc+ca)$ to both sides of the last equality and, applying our condition $a+b+c=20$ we obtain:

$$3(ab+bc+ca) = (a+b+c)^2 = 400$$

$$ ab+bc+ca = \frac{400}{3}$$

So having found that $\frac{400}{3}$ maximizes the LHS over $\mathbb{R}$ it follows that $\lfloor\frac{400}{3}\rfloor=133$ maximizes the LHS over $\mathbb{N}$.

It remains to find $a,b,c\in\mathbb{N}$ that satisfy both the above maximization condition and the condition: $a+b+c=20$.

We verify that for $(a,b,c)=(7,7,6)$ we indeed have the latter, and also:

$$ ab+bc+ca = 7\cdot7 + 7\cdot6 + 6\cdot7 = 133 $$

Thank you @CalvinLin for pointing out and helping me fix a serious mistake in the final part of the original answer!