Maximizing the Product: An Explanation

In my last two posts, I asked what the maximum product of integers adding up to 2017 was and then showed that the answer was $2^2\cdot 3^{671}$.

It was not clear at the beginning that the largest possible product would only use copies of two consecutive integers (2 and 3). In retrospect, we can see why that should have been the case. Suppose that our product used two integers, $A$ and $B$, that were not consecutive, so that $B-A\geq 2$. Then we could replace the $A$ and $B$ with $A+1$ and $B-1$, which have the same sum but a bigger product:

$$ (A+1)(B-1) = (A+1)B+(A+1)\cdot (-1) = AB\underbrace{+B-A}_{\text{at least }2}-1 > AB. $$

So, if our product had used non-consecutive integers, we could have improved upon it. Therefore, since the best product cannot be improved upon, its factors can only differ by 1.

If we weren’t limited to integers, we could push this idea even further. Suppose now that we want to maximize the product of real numbers that sum to 2017. I claim that we ought to use copies of a single number. To that end, consider a situation in which our product used two different numbers, $A$ and $B$. Then we could replace $A$ and $B$ with two copies of $\dfrac{A+B}{2}$ to get a larger product, because there is a theorem in mathematics called the AM-GM Inequality$^{[1]}$ that tells us that $$ AB < \left(\dfrac{A+B}{2}\right)^2 \text{ if }A\neq B .$$ Let’s stop and interpret what this inequality tells us: if we were to use two different integers in our product, then we could not possibly have found the largest one. Therefore, the biggest possible product must consist of copies of a single number.

Which single number should we use? Let’s call it $x$ for now, and we’ll figure out what $x$ ought to be. If all our copies of $x$ sum to 2017, then there must be $\dfrac{2017}{x}$ copies of $x$. (Ignore any issues about whether that division comes out cleanly.) The product we get is $x^{2017/x}$, or $(x^{1/x})^{2017}$. We can see when that product is largest by looking at the graph of the function $y=x^{1/x}$ and finding its highest point.

With the help of some calculus, we see that the highest point on this graph is when $x$ is equal to the mathematical constant $e$, which is approximately equal to $2.718$. The diagram below shows the graph from above zoomed in on the hump.

What this graph tells us is that if we weren’t restricted to integers, we would form the largest product by only using copies of $e$. But it also tells us how to handle the integer version of the problem as well. The graph of $y=x^{1/x}$ increased all the way up until $x=e$ and then decreased after that. So, the largest value of $x^{1/x}$ for integer values of $x$ has to happen at one of the integers on either side of $e$, $2$ and $3$. Of those two integers, we see that the graph is higher at $x=3$ than at $x=2$. So, if we can only use integers in our product, we should try to stick to copies of 3, resorting to 2s as necessary to round out the sum.

This solution is not quite as simple as the last one, since it relied on some tools of calculus, whereas the last one was strictly elementary. But it is an example of a fascinating problem-solving technique: to solve a problem about one kind of numbers, we first solve it in a much larger system and then use those insights to get the answer we originally wanted. Mathematicians have learned over the years that one of their most valuable tools is this kind of audacity.


$^{[1]}$ If you’ve never seen the AM-GM Inequality before, you can get a feel for it with a few examples. If $A=1$ and $B=5$, then the inequality it claims is $1\cdot 5<3^2$. If $A=3$ and $B=4$, then the inequality becomes $3\cdot 4<3.5^2$, or $12<12.25$. Both of these inequalities are true, which makes the AM-GM Inequality at least plausible. Mathematicians have proven that it always holds, no matter what $A$ and $B$ are, by using the tools of algebra and calculus.