On the board, we write the integers $1, 2, 3, \dots, 2019$. At each minute, we pick two numbers on the board $a$ and $b$, delete them, and write down the number $s(a + b)$ instead, where $s(n)$ denotes the sum of the digits of the integer $n$. Let $N$ be the last number on the board at the end. Is it possible to get $N = 19$? Is it possible to get $N = 15$?
Problem
Source: 2019 Pan-African Shortlist - C2
Tags: number theory, combinatorics, sum of digits
18.01.2021 04:59
a. We claim that the sum of the numbers on the board is invariant $\mod 9$. On any move, the sum of all the numbers on the board changes by $s(a+b)-a-b$, where $a$ and $b$ are the numbers involved. Since it is well known that the sum of the digits of any number is equal to the number $\mod 9$, the claim is proven. For $N=19$ to be possible, we need the sum of all numbers to be $1\pmod 9$. However, the sum of the numbers is actually $\frac{2019\cdot 2020}{2}=2019\cdot 1010\equiv 3\cdot 2=6 \pmod 9$, so it is impossible.
18.01.2021 05:17
b. We claim that it is possible. Combine the values $n$ and $2020-n$ for $1\le n \le 1009$ other than $n=9,60$. Then every combined value will be the sum of the digits of $2020$, which is $4$. The other values are $9,60,1010,1960,2011$. Then do $1010,1960,2011\rightarrow 1010, 20\rightarrow 4$. After this, we have $1008$ values of $4$, and one $9$ and one $60$. Only do operations that don't consist of the $9$ or the $60$ until there is only one number left other than these two. It is clear that doing this operation on two single-digit numbers must result in a single-digit number, so the final result must be a single digit. Because of the invariant, the sum of all numbers on the board must be $6\pmod 9$, and since the $9$ and the $60$ contribute $6\pmod 9$, the sum of the other numbers must be a multiple of $9$. However, since it must be a single-digit number, it must be either $0$ or $9$. Either way, combining this number with $9$ still gives $9$, and then combining the last two numbers $9,60$ gives us $15$, so it is possible.