# Partitioning a finite set which sums to $n$

Given $n > 1$, we consider the finite sets of positive integers which sum to $n$, and out of these sets we want to maximize the product. For example, given $n = 6$, the set $\{1, 5\}$ does not maximize the product, while the set $\{3, 3\}$ does.

How do I prove that for any given $n$, the set which maximizes the product does not contain any element greater than or equal to $4$?

I've started off with the basic idea that given $n$ is the sum, we can break $n$ up into the parts: $(n - x) + x$, where $x$ is some number between $0$ and $n$, non-inclusive of both.

Then the product becomes $(n - x)x$, and to maximize this function we take the derivative, find the critical point and find that this function is maximized when $x = \frac{n}{2}$.

But I'm not sure how to continue this process to prove that the greatest element in the set that maximizes the product is less than or equal to $4$?

Because my current attempt, for the example of $n = 12$, seems to yield that the maximum product is $6 \times 6$, not $3 \times 3 \times 3 \times 3$.

• A $4$ can occur, $\{3,4\}$ is a maximising partition of $7$. Of course, any $4$ can without loss converted to two $2$s, so we can avoid $4$, but we need to demand that to rule out $4$. Nov 5 '14 at 21:27
• Suppose in a partition there occurs a $k > 4$. Show that that partition is then not optimal. Similarly, if two or more $4$s occur, show that the partition is not optimal. Nov 5 '14 at 21:31
• Perhaps a better statement of what you want to prove is this: Let $n=\sum a_i$ be a partition of $n$ into positive integers with maximal product; that is, $n=\sum a_i$ has the property that for any partition $n=\sum b_i$ of $n$ into positive integers $b_i$, $\prod a_i\ge \prod b_i$. Then $\max a_i\le4$, and there exists a partition $n=\sum a'_i$ of $n$ into positive integers with $\max a'_i<4$ for which $\prod a'_i=\prod a_i$. Nov 5 '14 at 21:40

Suppose that our partition contains an entry $m\gt 4$. We show that it is profitable to split $m$.

It is convenient to divide into two cases, $m$ odd and $m$ even.

Suppose that $m$ is odd, say $m=2k+1$. We show that it is profitable to split $m$ as $k+(k+1)$. It is enough to show that $k(k+1)\gt 2k+1$, or equivalently that $k^2-k-1\gt 0$. Since $k\ge 2$, we have $k^2-k-1\ge 2k-k-1=k-1\gt 0$.

Suppose that $m$ is even, say $m=2k$. We show that it is profitable to split $m$ as $k+k$. It is enough to show that $k^2\gt 2k$, that is, that $k(k-2)\gt 0$. Since $k\ge 3$, this inequality holds.

As has been pointed out by Daniel Fischer, the case $m=4$ is special. We can either keep or split as $2+2$ without changing the product.

• More simply, if $m>4$, the product is not maximal. If we replace $m$ with $2+(m-2)$, the product becomes larger, because $2(m-2)=2m-4>8-4=4$. Nov 5 '14 at 21:45
• @SteveKass Good point, except that you want to prove $2(m-2)\gt m$, not $2(m-2)\gt4$. Of course that works too (for $m\gt4$) so the division into odd and even cases is unnecessary.
– bof
Nov 5 '14 at 21:56
• @SteveKass: I definitely gave a clumsy proof! My cheeks would be hot with shame if it were not for the fact that I am outside in the cold smoking. Nov 5 '14 at 21:56