An interesting problem with "decomposing" natural numbers.

Solution 1:

Here’s a visual proof, to complement the algebra of other answers:

When you start the game (from 20), draw a “staircase” shape like in the figure, but with 19 squares in the base (so also 19 squares high). As you play, for each number on the board you’ll always have a corresponding staircase, with base and height 1 less than that number. Each turn, when you split up a number as $n = b+c$, split up its staircase as shown in the picture; that gives you a $b \times c$ rectangle, plus two smaller staircases for the resulting numbers $b$ and $c$. The area of the rectangles is your score so far. When all the numbers left are 1’s, then you’ve converted the whole original staircase into rectangles — so your final score is the total area of the original staircase.

This area, the number of squares in the staircase of base $n-1$, is given by the formula $\frac{n(n-1)}{2}$, as noted in other answers. This is a famous formula, and if you haven’t seen it before, it can be explained by the fact that two such staircases fit together into an $n \times (n-1)$ rectangle.

Solution 2:

Suppose your hypothesis is that starting with $n$ you end up with a score of $\frac12 n(n-1)$. It is clearly true starting with $n=1$ as there are no moves and so a score of $0$.

Now suppose you know this is true for $1 \le n \le k$ for some $k$, then start with $k+1$ and split it into $a$ and $k+1-a$ where both are between $1$ and $k$. You get an immediate score of $a(k+1-a)$ plus (by the hypothesis) later scores of $\frac12 a(a-1)$ and $\frac12 (k+1-a)(k+1-a-1)$. Add these up and simplify to $\frac12 (k+1)k$. So it is true for $n=k+1$.

Using strong induction, you can conclude the hypothesis is true for all positive integers $n$.

Solution 3:

Suppose that we represent a number $n$ on the whiteboard by $n$ distinct objects. When we split $a$ into $b+c$, we put $b$ of the objects in one group, and $c$ of the objects in the other group.

Then we can represent the $b\cdot c$ points we get for the split as follows: for every pair of objects that used to be in the same group, but are now in different groups, we get a point.

At the beginning, all $20$ objects are in the same group. At the end, all $20$ objects are in different groups, so we must have gotten $\binom{20}{2}$ points for separating them.

Solution 4:

I turn my comment into an answer. Your conjecture is correct, and can be deduced with a proof by induction.

Claim: For $n>1$ the game always ends with the score $n(n-1)/2$.

Proof: Clear for $n=2$. So assume for numbers less than $n$ and start the game at $n$ with $n=a+b$ and score $ab$. You then continue with separate games on $a$ and $b$, which themselves end with score $a(a-1)/2$ and $b(b-1)/2$. So your final score is $ab+a(a-1)/2+b(b-1)/2=n(n-1)/2$.

Solution 5:

Compared to Misha Larov's answer, my solution has essentially the same idea but a different interpretation.

Let's say the number we start off with is $n$. At any stage of the game, we assign a complete graph $K_i$ to any number $i$ written on the board.

The action of splitting a number $a$ into $b$ and $c$ can be reinterpreted as

1. Choosing disjoint vertex subsets $B$ and $C$ of $K_a$ with respectively $b$ and $c$ elements
2. Deleting every edge connecting $i \in B$ and $j \in C$
3. Obtaining new complete graphs $K_b$ and $K_c$.

The score the player gets after this splitting is the number of edges deleted in step 2. Throughout the game, we actually count the total number of edges deleted.

At the final condition, where all graphs are $K_1$, which are individual vertices, we have eliminated all edges of the initial $K_n$. Hence the final score is always the number of edges in $K_n$, $\frac{n(n-1)}{2}$.