# Ten numbers on a blackboard

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.)

• 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? – Kevin Jan 14 '15 at 6:01
• @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. – xnor Jan 14 '15 at 6:07
• 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. – imallett Jan 14 '15 at 18:15
• @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. – xnor Jan 14 '15 at 23:41
• @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. – imallett Jan 15 '15 at 2:26

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$.

• I think this doesn't take care of the new created numbers in the process. – Avigrail Jan 13 '15 at 21:43
• 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$ – JonTheMon Jan 13 '15 at 21:58
• 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$. – theosza Jan 13 '15 at 22:33
• It's a change of basis! – Mehrdad Jan 14 '15 at 20:40

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$.