# Maximum operation order for a set of integers

Say we are given the positive integers $[1,1,2,2,3]$

We want to know what the maximum number is using only the operators $+$, $\times$.

For this set the maximum operation is $(2+1)\times(2+1)\times3=27$

Now obviously we can see that if there is no number smaller $2$, we just have to calculate the product of those numbers.

Next for any number of $1$s we have to build the maximum amount of $3$s avoiding having a leftover $1$. So $[1,1,1,2]=(1+1+1)\times2=6$. Now my question is: Why is building $3$s the best possible strategy? Does there exist any formal proof as why this strategy works?

This question was inspired by this challenge.

Regarding the tagging: I have absolutely no idea which tags are appropriate, so if you happen know fitting tags, feel free to retag.

• Hmm...I suspect that it's because $3$ is the closest integer to $e$. – Adriano Aug 29 '14 at 21:56
• @Adriano I suspect that too, but why? – ThreeFx Aug 29 '14 at 22:00

I think it's fairly trivial that if there are no $1$s, then the best strategy is to multiply the numbers as you said. The question is what to do when there are $1$s.
Let's say that you have a $1$ in your array and you also have an $n$. The default strategy is to multiply all the numbers greater than $1$, so we're trying to decide where to add the $1$. If you add $1$ to $n$, then it's like you're dividing out the factor $n$ and multiplying in an $n+1$. The goal, then, is to maximize the ratio $\frac{n+1}{n}$.
I'll use $[1,2,3,4]$ as an example. The product is $2 \times 3 \times 4 =24$. If you add the $1$ the one to the $4$, for instance, now your product is $2 \times 3 \times 4 \times \frac{5}{4} = 2 \times 3 \times 5 = 30$.
But clearly we're going to get the best results when the ratio of $n$ and $n+1$ is large, so we add our $1$ to the smallest factor there is. So the result is $2 \times 3 \times 4 \times \frac{3}{2} = 3 \times 3 \times 4 = 36$.
Why isn't it a good strategy to add $1$ to itself? Doing so creates a $2$, which lets you double your product, but it uses up two of your $1$s. Adding a $1$ to a $2$ increases the product by 50%, and doing that twice gives you $150\% * 150\% = 225\%$, which is better than doubling.