Maximizing the product of $k$ positive integers where the sum is equal to $n$

Question

Question: Given an integer $n$, break it into the sum of $k$ positive integers, where $k \geq 2$, and maximize the product of those integers.

Return the maximum product you can get.

Comment:

The key observation is the fact that for any integer $n \geq 4$, it has the property such that $3\cdot(n - 3) > n$ which means breaking it into two integers $3$ and $n - 3$ makes the product larger while keeping the sum unchanged.

If $n - 3$ is still greater than $4$, we can break it into $3$ and $n - 6$, resulting in $3 \cdot 3 \cdot (n - 6)$ and so on, until we cannot break it (less than or equal to $4$) anymore.

I was just wondering, why is the above observation true/valid, from an academic/mathematical perspective

Answer 1

Take $n = 10$ and $k = 4$ for example. If we use your method, we have $3 \cdot 3 \cdot 3 \cdot 1 = 27$. If we try another way, we can have $2 \cdot 2 \cdot 3 \cdot 3 = 36$.

---

My hypothesis (without the $k$ constraint):

To maximize, break $n$ into $\lfloor\frac{n}{2}\rfloor$ and $\lceil\frac{n}{2}\rceil$. Then, for each number, repeat until the number is either $2$, $3$, or $4$.

The reason why $2$ should not be broken is because it breaks into two $1$'s, and the product is $1$ which is less than $2$. For $3$, the maximum product if broken is $2$ which is less than $3$. For $4$, the maximum product is $4$ since $2 + 2 = 4$ and $2 \cdot 2 = 4$.

Let's have $n = 25$. Breaking it, we have $12$ and $13$. Breaking $12$, we have two $6$'s, where breaking $6$ gives two $3$'s. Hence, $12$ breaks into $[3,3,3,3]$. Breaking $13$, we have $6$ and $7$. Breaking $6$ gives two $3$'s and breaking $7$ gives $3$ and $4$. Hence, $13$ breaks into $[3, 3, 3, 4]$.

Multiplying all, we have $3^{7}\cdot 4 = 8748$.

I am still trying to prove that this is true. Hopefully, someone might do it.

---

With the $k$ constraint, the maximum product is $(\lfloor\frac{n}{k}\rfloor)^{k - (n \bmod k)}(\lfloor\frac{n}{k}\rfloor + 1)^{(n \bmod k)}$ where $0 \leq (n \bmod k) < n$. In my example where $n = 10$ and $k = 4$, $10 \bmod 4 = 2$, hence the maximum product is $2^{4 - 2}(2 + 1)^{2} = 2^{2}3^{2}$. In @user64494 's example where $n = 40$ and $k = 6$, $40 \bmod 6 = 4$, hence $6^{6 - 4}(6 + 1)^{4} = 6^{2}7^{4}$. I don't know how to prove this if this gives the maximum product. This was already mentioned by @MatthewLeingang .

Answer 2

You may play with it, making use of Mathematica, e.g.

n = 10; k = 4; NMaximize[{Product[x[j], {j, 1, k}], Sum[x[j], {j, 1, k}] == n, 
Table[x[j], {j, 1, k}] \[Element] PositiveIntegers}, Table[x[j], {j, 1, k}], 
Method -> "DifferentialEvolution", AccuracyGoal -> 4, PrecisionGoal -> 4, MaxIterations -> 1000]

{36., {x[1] -> 3, x[2] -> 2, x[3] -> 2, x[4] -> 3}}

For $n=40$ and & k=6$ we obtain {86436.,{x[1]->7,x[2]->7,x[3]->7,x[4]->6,x[5]->7,x[6]->6}}.

Answer 3

To build on soupless's answer, you want your numbers to be as close together as possible to maximize their product. That's a calculus problem, which can be solved using Lagrange multipliers.

For integers, it's a bit trickier, since you can't necessarily make them all the same (only when $k$ is a factor of $n$ can you do so). Given $n$ and $k$, there exist $q$ and $r$ such that $n=kq+r$ and $0 \leq r < k$. We claim the product is maximized by making $r$ numbers equal to $q+1$ and $k-r$ of them equal to $q$. This partition is characterized by the property that each of the numbers is between $q$ and $q+1$, and they all add up to $n$.

If, as in the first of soupless's examples, $n=10$ and $k=4$, then $q=2$ and $r=2$. The method predicts that the product is maximized with two $3$'s and two $2$'s. Or user64494's example of $n=40$ and $k=6$. Then $q=6$ and $r=4$, and the maximum product predicted is $7^4 6^2 = 86,436$.

Why is this partition maximal? Suppose we were given a partition of $n$ for which at least one of the $k$ numbers, call it $n_1$, were strictly less than $q$. Then one of the numbers, call it $n_2$, must be strictly greater than $q$, otherwise the sum would be less than $kq$, and $n \geq kq$. So $n_1 \leq q-1$ and $n_2 \geq q+1$, meaning $n_2 - n_1 \geq 2$.

Create a new partition that replaces $n_1$ with $n_1' = n_1+1$ and $n_2$ with $n_2' = n_2 - 1$, but leaves the other numbers the same. Then $$ n_1'n_2' = (n_1 + 1)(n_2-1) = n_1 n_2 + (n_2 - n_1) - 1 \geq n_1n_2 +1 $$ This means the product of the numbers in the new partition is larger, and so the given partition is not maximal.

Similarly, one should be able to argue that if one of the numbers is more than $q+1$, then one of them is less than $q+1$, and borrowing one from the greater to give to the lesser will make the product greater.

---

Having completed this answer, I see you might be interested in maximizing over $k$, too. If that's true, I'd have to think more about that.

Answer 4

We want to find the maximal value of $a_1\times \dots \times a_k$, ranging over all integers $k\ge 2$ and tuples $(a_1,\dots,a_k)$ of positive integers for which $a_1+\dots+a_k=n$. This is a problem in discrete optimization.

You ask why the observation $3\cdot (n-3)>n$ is true/valid. This is not an interesting question, as it simply boils down to $3n-9>n$, which is true whenever $n>4.5$, equivalent to $n\ge 5$ over the integers. What is interesting is how you can use this observation to determine the maximal tuple. Let us start by ruling out some non-maximal tuples.

• Any tuple with an entry $k$ for which $k\ge 5$ can be ruled out, for the reasons discussed.

• All that remains are tuples with entries in $\{1,2,3,4\}$. We can further rule out any tuple with a $1$, since $1\cdot k<(k+1)$, so it is better to merge the $1$ with another entry.

• All that remains are tuples with entries in $\{2,3,4\}$. We can rule out any tuple with three or more $2$'s, since it is better to replace $(2,2,2)$ with $(3,3)$. Further more, we can rule out tuples with two or more $4$'s, since it is better to replace $(4,4)$ with $(3,3,2)$. Finally, you cannot have a $2$ and $4$ simultaneously, since $(3,3)$ is better than $(2,4)$.

• The only remaining tuples have a bunch of $3$'s, and possibly one or two $2$'s or a $4$. That is, the maximal tuple can only be $$ (3,3,\dots,3)\qquad (3,3,\dots,3,2)\qquad \begin{matrix} (3,3,\dots,3,4)\,\,\,\,\,\\ (3,3,\dots,3,2,2) \end{matrix} $$

The last two tuples in the last column have the same product. Other than that, the tuples in all three columns have distinct sums modulo $3$. It follows that any given $n$ corresponds to the sum of the tuple(s) in exactly one of those columns, so that the maximal tuple is unique (except for when $n\equiv 1\pmod 3$, in which case there are two maximal tuples).