Combinatorics Problem: Building numbers from the difference of the first 2021 numbers

Question

I recently found this problem, it was part of a regional qualifier in Southern America (Venezuela- I believe) in January 2021. As I can’t find the solution anywhere and it is very different from the problems I have tackled so far I thought I might ask you all for some help. I have tried finding cases where $(a)$ or $(b)$ is true, but I wasn’t able to do that.

THE PROBLEM:

On a blackboard are the numbers $1, 2, . . . , 2020$ and $2021$. The following operation is carried out: You choose two numbers, write the amount of their difference on the board and delete the two numbers chosen. Repeat this until there is only one number left on the board.

$(a)$ Show that $2021$ can be the last number on the board.

$(b)$ Show that $2020$ cannot be the last number on the board.

Answer 1

$(a)$ First step, choosing $(1,2), (3,4),...,(2019,2020)$. After these operations, the remaining numbers on the board are 1010 times of ones and $2021$. Second step, choosing $(1,1),...(1,1)$ ($\frac{1010}{2} = 505$ couple $(1,1)$), the remaining numbers on the board are 505 times of zeros and $2021$. Now, it suffices to choose whatever two numbers on the board. $2021$ will always be the last number on the board.

$(b)$ We notice that there are an odd numbers of odd numbers ($1011$ odd numbers). After every operation, the number of odd numbers must always be odd, because: \begin{cases} odd-odd =even \qquad \#OddNumber \text{ reduces 2}\\ odd-even =odd \qquad \#OddNumber \text{ is unchanged}\\ even-even =even \qquad \#OddNumber \text{ is unchanged}\\ \end{cases}

If the end, $2020$ is the remaining number, then the number of odd number is even (there is $0$ odd numbers) $\implies$ contracdiction.

So, $2020$ cannot be the last number on the board.

Answer 2

The given operation preserves the parity of the number of odd numbers on the board -- that number always drops either by $2$ or $0$. Since you started with an odd number of odd numbers, it's impossible for $2020$ to be the last number on the board.

As for the first part, just pair up numbers in order: $1$ and $2$, $3$ and $4, \ldots$. You'll get a string of an even number of $1$s followed by $2021$. Now pair up the $1$s and you'll get a string of $0$s followed by $2021$. Now eliminate $0$s until you're left with $0$ and $2021$.