Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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?

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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