4
$\begingroup$

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.

1 Answers 1

2

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?

  • 0
    @metafour No, it was not very clear that you were saying that. But I think you got what to do. Alternatively, you can *without loss of generality*, always split $4$ as $2+2$ in the beginning. Now, you have a factorization where (1) 1 does not occur (2) > 4 does not occur, (3) 4 also does not occur. That is, you have a bunch of 2s and 3s. Now, you know what to do.2011-09-06