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.

• Well, to see that the result (if it exists) can only be $2019$, work inductively. Do the game $G_n$ with $1, \frac 12, \cdots ,\frac 1n$. Easy to see that $G_2$ ends in $2$. Assume that $G_n$ ends in $n$. Then, to do $G_{n+1}$ you first play the game $G_n$, leaving you with $n$ and $\frac 1{n+1}$. But $n+\frac 1{n+1}+\frac n{n+1}=n+1$ as desired. You still need to show that the order in which you do things doesn't matter, however.
– lulu
Commented Aug 31, 2019 at 22:17
• Yeah, that’s the thing, I don’t think is induction because at my level we are not supposed to know that or solve these problems with those methods, I think its something simpler. But thanks for the response. Commented Aug 31, 2019 at 22:25
• The result will be $(1+1/1)(1+1/2)\cdots(1+1/2019)-1=2019.$ If we define the uperation $*$ as $a*b=(1+a)(1+b)-1$ then $*$ is commutative and associative. Commented Aug 31, 2019 at 22:29

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.

• Excellent answer, thanks a lot. Nice to see that it had something to do with factoring. I think Invariance is a really powerful method. I saw 3blue1browns’s video of the IMO problem and was amazed. Commented Aug 31, 2019 at 22:53
• That "and therefore" in the middle (lines 3-4) bewilders me. Care about fleshing that out a bit? Commented Aug 31, 2019 at 23:05
• Without loss of generality, assume that $a_i$ and $a_j$ are in fact $a_1$ and $a_2$ (to make writing this up easier). Then, notice how when they erase $a_1$ and $a_2$, the new term, $a_n = a_1a_2 + a_1 + a_2$, and therefore $a_n + 1 = a_1a_2 + a_1 + a_2 + 1 = (a_1+1)(a_2+1)$ so the two produts are equal. Commented Sep 1, 2019 at 1:53

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.