46
$\begingroup$

The numbers 1 through 10 are written on a blackboard. You erase two numbers of your choice, and write their product plus their sum

$$a,b \to ab+a+b$$

So, now there are nine numbers on the board. You repeat this process until a single number remains. What is the largest this number can be?

(I can't stop you from writing code to brute-force this, but I assure you there's a nice solution and coding isn't needed.)

Improve this question
$\endgroup$
7
  • $\begingroup$ I don't understand what you do with $ab+a+b$ once you've calculated it. When you've picked a third number $c$, do you then calculate, for example, $c(ab+a+b)+c+(ab+a+b)$, then continue recursively applying the operation with the subsequent numbers you select? $\endgroup$
    – Kevin
    Jan 14, 2015 at 6:01
  • 2
    $\begingroup$ @Kevin Now $c$ is a new number of the blackboard. You can do a new operation with it as you said, or you can take two different numbers save $c$ for later. $\endgroup$
    – xnor
    Jan 14, 2015 at 6:07
  • 1
    $\begingroup$ For what it's worth, after reading the answers I decided to see how long a brute force program would take. My solution takes 0.43 seconds on the analogous problem of length 7, 12.3 seconds for length 8, and 442.1 seconds for length 9. I didn't let it run for length 10. $\endgroup$
    – geometrian
    Jan 14, 2015 at 18:15
  • $\begingroup$ @imallett Are you taking advantage of the fact that, say, erasing 1 and 2, then erasing 3 and 4, is the same as doing the two in the opposite order? If you do, the possibilities correspond to full binary trees on ten nodes, of which the number is the tenth Catalan number 16796, well in range of brute force. $\endgroup$
    – xnor
    Jan 14, 2015 at 23:41
  • $\begingroup$ @xnor, from your codegolf account, I know you use Python--why not look yourself? :) But yes, the code only considers half the possibilities. It's still O(n^2) possible eliminations, though. The larger problem is that Python is relatively slow, and my implementation is a brick-dumb recursive algorithm written for clarity. My conclusion is that 10 is well within the range of commodity brute force (by one of my estimates, 5½ hours would have been enough), but that math is a better tool. $\endgroup$
    – geometrian
    Jan 15, 2015 at 2:26

2 Answers 2

Reset to default
54
$\begingroup$

Let the combining operation be $\otimes$, i.e. $a \otimes b = ab + a + b$.

Observe the following for $\otimes$: $$a \otimes b + 1\\ = ab + a + b + 1\\ = (a + 1)(b + 1)$$ So the ordinary multiplication operation is equivalent to $\otimes$ just offset by $+1$. This suggests an equivalent formulation of the problem where instead of working on the original values 1 through 10, we work with 2 through 11 and just use multiplication. Our answer will end up being 1 larger than that required by the original problem.

Since multiplication is commutative and associative, the ordering doesn't matter and all possible sequences will give us the same answer.

The solution to this transposed problem is then $2 \times 3 \times 4 \times \ldots \times 11 = 11! = 39916800$.

And so the solution to the original problem is $1 \otimes 2 \otimes 3 \otimes \ldots \otimes 10 = 11! - 1 = 39916799$.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ I think this doesn't take care of the new created numbers in the process. $\endgroup$
    – Avigrail
    Jan 13, 2015 at 21:43
  • 9
    $\begingroup$ I think it does. Take numbers $a$ and $b$. Those would add up to $(a+1)(b+1)-1$. Now mix with number $c$: You'd have $(c+1)([(a+1)(b+1)-1]+1)-1 = (c+1)(a+1)(b+1)-1$ $\endgroup$
    – JonTheMon
    Jan 13, 2015 at 21:58
  • 7
    $\begingroup$ It's easy enough to verify with smaller values. You can try all possible orderings for 1, 2, 3 and you always end up with $23 = 4! - 1$. $\endgroup$
    – theosza
    Jan 13, 2015 at 22:33
  • 3
    $\begingroup$ It's a change of basis! $\endgroup$
    – user541686
    Jan 14, 2015 at 20:40
23
$\begingroup$

The largest it can be is actually also the smallest it can be. In fact, if the numbers 1 through $n$ are written and the same process followed, the end result will be $(n+1)! - 1$ no matter what order you combine numbers.

Let's take a smaller set, just $\{a, b, c\}$, to see why. If you group $a$ and $b$ first, you'll end up with $$ (ab+a+b)c+(ab+a+b)+c=a+b+c+ab+ac+bc+abc $$ If you group $b$ and $c$ first, you get $$ (bc+b+c)a+(bc+b+c)+a=a+b+c+ab+ac+bc+abc $$ And just for completeness, grouping $a$ and $c$ first gives $$ (ac+a+c)b+(ac+a+c)+b=a+b+c+ab+ac+bc+abc $$ At the end of the $n$ numbers, you will always end up with the sum of the individual numbers, plus the sum of the products of the numbers taken 2 at a time, plus the sum of the products taken 3 at a time, all the way up to the product of all the numbers. If you added 1 to the final sum, you could factor the final result into $(a+1)(b+1)(c+1)...$ giving $(n+1)!$ in this case.

Similarly, a starting list of the number $k$ written $n$ times will result in $(k+1)^n-1$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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