An interesting problem with "decomposing" natural numbers.

Question

Consider the following one-person game:

A player starts with score $0$ and writes the number $20$ on an empty whiteboard. At each step, she may erase any one integer (call it $a$) and writes two positive integers (call them $b$ and $c$) such that $b + c = a$. The player then adds $b × c$ to her score. She repeats the step several times until she ends up with all $1$s on the whiteboard. Then the game is over, and the final score is calculated.

Example: At the first step, a player erases $20$ and writes $14$ and $6$, and gets a score of $14 × 6 = 84$. In the next step, she erases $14$, writes $9$ and $5$, and adds $9 × 5 = 45$ to her score. Her score is now $84 + 45 = 129$. In the next step, she may erase any of the remaining numbers on the whiteboard: $5$, $6$ or $9$. She continues until the game is over.

Alya and Bob play the game separately. Alya manages to get the highest possible final score. Bob, however, manages to get the lowest possible final score. What is the difference between Alya’s and Bob’s final scores?

I tried to "decompose" into a few numbers and I get the same scores. I am not sure how to prove the conjecture that any numbers will yield the same score no matter which path is taken.

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

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

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

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

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