Math question: You are allowed to take as many (positive) whole numbers as you want that add up to 20, and then multiply them together. What is the biggest possible result you can get?

20? Why 20? That’s a number both boring and small. Imagine that we are allowed to take as many whole numbers as we want that add up to a trillion, and then multiply them together. What is the biggest possible result we can get?

Of course, I don’t really mean a trillion. What I mean is N, an arbitrary positive integer. We need to maximize the product of some whole numbers (positive integers) adding up to N. Yes, we will solve infinitely many versions of this problem, not merely the one with 20.

In school, many of us learn techniques for solving optimization problems using derivatives. There are several obvious problems with such an approach here: the unknowns are whole numbers, rather than real numbers; we have an unknown number of unknowns; and if you are early in your study of calculus, you may be unsure how to maximize a function of several variables.

There’s an approach to this problem that I won’t spend too much time on but is worth mentioning: you can try to ignore some of these problems. Imagine the numbers are real, instead of being positive integers, and imagine that you do know how many there are. What happens then?

You may be able to deduce that the best way to maximize a product given a fixed sum is to make all variables equal. So, if you decided to have k numbers, the maximal product will be (N/k)^k. All that’s left to do is find the optimal k, which is a fun problem in and of itself. You can once again ignore the fact that k is an integer; for a real variable, this is maximized when N/k=e, Euler’s constant. Our incorrect approach seems to give us a clue: we want the numbers to be close to e. This turns out to be correct, although we don’t know that yet.

The actual, successful approach is simply to consider small, local changes. Here’s what I mean by that.

Suppose someone claims that they have the best list of numbers which add up to N, “best” meaning having maximum product, of course. Could that best list possibly include a 17?

You may be thinking, sure, why not? Here’s why not: if your buddy says they have the best list and it has a 17, you can immediately make a better list by replacing that 17 with an 8 and a 9. Did you change the sum? Not at all. 8+9 is still 17. Did you change the product? Yes, and you can see exactly how: the product used to be something times something times 17 times blah blah, and now it’s something times something times 72 times blah blah. That’s much bigger!

Conclusion: the number 17 cannot possibly be a member of a winning team. Is that a special feature of 17? No, of course not. 53 can’t be there either, nor can 12 or 7 or 5. If you have any number x which is at least 5, you can replace it by the pair x-2, 2 which keeps the sum intact but increases the product from having an x to having a 2x-4. This 2x-4 is more than x (because x is at least 5) so the replacement pays off.

We’ve made tremendous progress: the optimal solution, whatever it is, must comprise exclusively 1's, 2's, 3's and 4's.

Wait. Do we really need 4's? Any 4 can be replaced by a pair of 2's. That doesn’t change the sum, and although it doesn’t improve the product, it doesn’t hurt either. Whatever the optimal solution is, it doesn’t need to have any 4's.

And of course, we don’t want any 1's, too. I mean, if N=1 then we have no choice, but for any larger N, keeping any 1's around isn’t a mark of high intelligence. Any 1 along with some other x can be replaced with an x+1. Same sum, larger product.

So: our optimal product is made up exclusively of 2's and 3's. Remember when we said that the best thing to do is stay close to e? There you go.

Now, how many 2's and how many 3's do we want? Here’s the final key observation: if you have 2,2,2, you should replace them with 3,3. The sum stays intact but the product just increased by a factor of \frac{9}{8}.

So we are allowed to keep some 2's around, but not too many: at most two of them. Everything else should be a 3. Once again, glimpses of that mystic e, closer to 3 than it is to 2.

So do we want no 2's at all? Or one of them? Or two? Fun fact: we don’t need to figure that out, since N forces the number of 2's. If N is divisible by 3, the number of 2's cannot be one or two: it has to be none at all, or three, or six, and so on; but we already know that three 2's are useless, so we simply need none.

Similarly, if n leaves a remainder of 2 upon division by 3, we will want a single 2, while if n leaves a remainder of 1 upon division by 3, we will need two 2's to make the sum work.

That’s it! We’ve solved the problem in complete generality: the maximal product of positive integers whose sum is N is obtained as follows.

• If N=3m, take m 3's to obtain a product of 3^m.
• If N=3m+1, take (m-1) 3's and two 2's, to get 4 \times 3^{m-1} = \left(\frac{4}{3}\right)\times 3^m.
• If N=3m+2, take m 3's and a single 2 to get a product of 2 \times 3^m.

For the original problem with N=20, the maximal product is therefore 2 \times 3^6 = 1458. If N=100, which is how I usually ask the question, the maximal product is 4 \times 3^{32}. And if N=10^{12}, a trillion, the maximal product is 4 \times 3^{333333333332}. You can even determine the largest possible product for a bunch of positive integers whose sum is googolplex.

That’s all – we’ve just solved an optimization problem involving an unknown number of integer unknowns!