4
$\begingroup$

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.

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

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.

$\endgroup$

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.