Olympiad Algebra Practice Question

Let the terms on the board in any given move be $a_1, a_2, a_3, a_4 ... a_n$. We will prove that $(1+a_1)(1+a_2)(1+a_3)....(1+a_n)-1$ never changes, and therefore is an invariant.

First, consider any move, with $a_i$ and $a_j$. Notice that $(1+a_i)(1+a_j) = 1+a_i+a_j+a_ia_j$, and therefore the value of $(1+a_1)(1+a_2)(1+a_3)....(1+a_n)-1$ constant.

Let the value that Martin gets at the end be $n$. Notice that $(1+\frac{1}{1})(1+\frac{1}{2})...(1+\frac{1}{2019})-1 = \frac{2}{1}\frac{3}{2}....\frac{2020}{2019} - 1 = (1 + n) - 1 \implies n = 2019$, so we are done.

I think I have an (admittedly less elegant) answer not involving an invariant.

Suppose that Vincent always erases the two leftmost numbers, and writes the result in the leftmost position. We will first show that the order of the numbers doesn't matter. Suppose the blackboard is like this at some step :

$$ \begin{aligned} a_1 && a_2 && a_3 && \ldots \end{aligned} $$ If we swap $a_1$ and $a_2$, the state of the board after our next move doesn't change, as $a_1 + a_2 + a_1a_2 = a_2 + a_1 + a_2a_1$. If we swap $a_2$ and $a_3$, the temporary result of $a_1 + a_3 + a_1a_3$ does change, but the final result after having computed the next two moves doesn't change - it is $a_1 + a_2 + a_3 + a_1a_2 + a_1a_3 + a_2a_3 + a_1a_2a_3$ anyway. The same line of reasoning holds for any swap. The underlying formal cause is that the operation is associative.

But any configuration can be attained by simply swapping two adjacent numbers enough times, even in the middle of processing a string, for we can move a given number at any position, and thus the one corresponding to the way Vincent proceeded. So, order doesn't matter and we only need to compute the result e.g. when all the numbers are arranged in decreasing order. Let us show that by induction. Let $S_n$ be the result with $n$ numbers.

For $n = 1$, we only have one number on the blackboard, and it is 1. So $S_1 = 1$.
Suppose $S_k = k$ for some $k$. Then, when we compute $S_{k + 1}$, before the second to last move we will have a blackboard like : $$ \begin{aligned} S_k && \frac{1}{k + 1} \end{aligned} $$ That is, by our hypothesis on $k$ : $$ \begin{aligned} k && \frac{1}{k + 1} \end{aligned} $$ However, $k + \frac{1}{k + 1} + \frac{k}{k + 1} = k + 1$, and thus, if $k$ is such that $S_k = k$, then $S_{k + 1} = k + 1$. By induction, we conclude that Martin had predicted 2019.