Olympiad Algebra Practice Question

Question

I just needed some help for this problem they gave us at our mathematics class, its’s an Olympiad type question, I suspect the answer is 2019, I tried with smaller cases and tried to use a recursive relation, or some type of induction. I also tried factoring by noticing that $a+b+ab=(a+1)(b+1)-1$ but couldn’t manage to solve it. Hoping someone could help. Here is the problem:

Martin wrote the following list of numbers on a whiteboard:

$$1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \frac{1}{5},...,\frac{1}{2019}$$

Martin asked for a volunteer. Vincent offered to play, Martin explained the rules to Vincent. Vincent has to choose two of the numbers on the board, lets say $a$ and $b$. He has to wipe off these numbers and write the number $a+b+ab$ on the board.

For example, if Vincent would have chosen $\frac{1}{2}$ and $\frac{1}{3}$, he would wipe these numbers off and write $\frac{1}{2}+\frac{1}{3}+\frac{1}{2}·\frac{1}{3}=1$ on the board. Then the board would look like this:

$$1, 1, \frac{1}{4}, \frac{1}{5},...,\frac{1}{2019}$$

Martin asked Vincent to do this over and over again choosing any two numbers each time, until only one number was left. When Vincent was done, Martin asked him to open an envelope where he had written a prediction, Vincent opened it and was surprised to find that the number on the whiteboard and on the envelope were the same.

What was Martin’s prediction? Justify your answer.

Answer 1

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.

Answer 2

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.