The numbers $1, 2, ..., 2020$ and $2021$ are written on a blackboard. The following operation is executed: Two numbers are chosen, both are erased and replaced by the absolute value of their difference. This operation is repeated until there is only one number left on the blackboard. (a) Show that $2021$ can be the final number on the blackboard. (b) Show that $2020$ cannot be the final number on the blackboard. (Karl Czakler)
Problem
Source: 2021 Austrian Regional Competition For Advanced Students p3
Tags: number theory, game, combinatorics
01.06.2021 02:21
02.06.2021 04:26
This might be a dumb question but how does the fact that there are 1011 odd numbers imply that there cannot be 2020 on the board alone. How is this justified by writing that this would imply that there is an even amount of odd numbers on the board.
02.06.2021 06:40
In other words, what kankan means for part b is that under the operation $a,b \rightarrow |a-b|$, the sum of all the elements in the list is invariant mod 2, i.e. $|a-b|\equiv a-b \equiv a+b $ mod 2, which means that the last element on the list after 2020 moves must be congruent mod 2 to the original sum, which is $1+2+...+2021=\frac{(2021)(2022)}{2} = (2021)(1011)$ which is odd, so the last number cannot be 2020.
16.10.2024 10:20