# Proof of max product of partitions of n

For $n \in \mathbb{Z} : n \geq 1$

$f(n) = \displaystyle\max_{\substack{ x_1+\dotsm+x_k = n\\ x_i\in\mathbb{Z}^{+} }} x_1 x_2 \dotsm x_k$

$$f(n) = \begin{cases} 1 & \text{if n = 1}, \\ 3^{\left\lfloor\frac{n}{3}\right\rfloor}& \text{if n \mod 3 = 0},\\ 3^{\left\lfloor\frac{n}{3}\right\rfloor-1} \cdot 2^2& \text{if n \mod 3 = 1},\\ 3^{\left\lfloor\frac{n}{3}\right\rfloor} \cdot 2& \text{if n \mod 3 = 2}, \end{cases}$$

Proof:

First observe that for any $x_i = 1$ in our product we do not increase the value of the final product. Therefore we want $x_i > 1$. However, for any set of three $x_i = 2$ we want to refactor this set into two $x_i = 3$ since $3\cdot3 > 2\cdot2\cdot2$. Now, for any $x_i > 4$ observe that $2(x_i-2) = 2x_i - 4 > x_i$. Thus to maximize our product we have at most two 2's and as many 3's as possible.

What is my proof possibly missing?

Here's an updated proof.

Proof:

First observe that for any $x_i = 1$ in our product we do not increase the value of the final product. Therefore we want $x_i > 1$. However, for any set of three $x_i = 2$ we want to refactor this set into two $x_i = 3$ since $3*3 > 2*2*2$. Now, for any $x_i > 4$ observe that subtracting 2 from our term increases our total product. That is $2(x_i-2) = 2x_i - 4 > x_i$ for $x_i > 4$. We can repeat this process until $x_i \leq 4$ and this limits our individual factors to being no greater than 4. For any $x_i = 4$ where there are no existing factors equal to 2 we do not necessarily need to factor this into $2 \cdot 2$ since this product is equal to $4$ and will not increase our total product. Thus to maximize our product we have at most two 2's, or a single 4, and as many 3's as possible. This leads to our piecewise defined function. For any n divisible by 3 we will have a product comprised of 3 raised to the power $\frac{n}{3}$. If we have a remainder of 1 when dividing n by 3 we want one less factor of 3 than $\frac{n}{3}$ provides so that we can create a factor of $2^2$ or $4$. Finally, if n divided by 3 has a remainder of 2 we will just include the remainder as a factor in our final product.

-

Your overall proof strategy looks good. But I found two problems with the proof.

First a nitpick. Look at your sentence:

Now, for any $x_i > 4$, observe that $2(x_i - 2) = 2x_i-4 > x_i$.

I do not immediately see what to conclude from this observation, or why I must conclude that. Using this argument, I presume you are convincing me that none of the factors can be $> 4$, but this was not explicitly stated anywhere. Neither is the justification immediately clear. I would therefore rewrite this to:

Now, if any $x_i > 4$, then splitting $x_i$ into a pair of factors, namely $2$ and $x_i - 2$, would strictly increase the product, since $2(x_i - 4) = 2x_i - 4 > x_i$. Hence none of the factors can exceed $4$.

Now, a gap in the proof. Your argument leaves out the possibility that some of the factors are $4$. Now, it is wrong to claim that $4$ cannot appear as a factor in the largest product; for example, if $n = 7$, then the partitions $\{ 3, 2, 2 \}$ and $\{ 3,4 \}$ have the same product of $12$, which is also the best possible.

So what is the correct way to handle the factors of $4$? Taking a clue from the $x_i > 4$ case, I would think that splitting $4$ as $2+2$ would be of some help. Can you complete the argument for this case?

-
I think there could also be a step from "at most two 2s [or one 4] and as many 3s as possible" to the formulae modulo 3. –  Henry Sep 6 '11 at 10:50
Yes, now that you point out, that needs some explanation at least. (I guess all these make sense, depending on at what level the proof is supposed to be.) –  Srivatsan Sep 6 '11 at 14:05
I've updated my proof and hopefully it addresses everyone's concerns. Thanks for the feedback! –  metafour Sep 6 '11 at 20:30
@metafour Your new proof still does not handle 4 properly. If $n=11$, your solution allows the partition $\lbrace 2,2,4,3 \rbrace$ as a possible partition with maximum product. But is this optimal? –  Srivatsan Sep 6 '11 at 20:37
@Srivatsan The second sentence mentions what to do in the case of any set of three 2's, refractor $2*2*2$ into $3*3$. My mention of $x_i=4$ specifically calls out that if there are no other factors equal to 2 we don't need to do anything. However, if there are other factors of two are you saying it's not clear that the implication is to factor that into $2*2$ and then refactor according to the second sentence? –  metafour Sep 6 '11 at 21:20