2
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$ Nov 5 '14 at 21:27
  • $\begingroup$ 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. $\endgroup$ Nov 5 '14 at 21:31
  • $\begingroup$ 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$. $\endgroup$
    – Steve Kass
    Nov 5 '14 at 21:40
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$
    – Steve Kass
    Nov 5 '14 at 21:45
  • $\begingroup$ @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. $\endgroup$
    – bof
    Nov 5 '14 at 21:56
  • $\begingroup$ @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. $\endgroup$ Nov 5 '14 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.