Problem 1. Every positive integer is marked with a number from the set $\{0,1,2\}$, according to the following rule:

$$
\text { if a positive integer } k \text { is marked with } j \text {, then the integer } k+j \text { is marked with } 0 \text {. }
$$

Let $S$ denote the sum of marks of the first 2019 positive integers. Determine the maximum possible value of $S$.

(Ivan Novak)
First Solution. Consider an arbitrary marking scheme which follows the given rule.

Let $a$ denote the number of positive integers from the set $\{1, \ldots, 2019\}$ which are marked with a $2, b$ the number of those marked with a 1 , and $c$ the number of those marked with a 0.

1 point.

We have $S=2 a+b$.

1 point.

For every positive integer $j \in\{1, \ldots, 2017\}$ which is marked with a 2 , the number $j+2$ is marked with a 0 . This implies that the number of positive integers less than 2017 marked with 2 is less than or equal to $c$.

1 point.

Hence, this implies $a \leqslant c+2$. We then have

$$
S=2 a+b \leqslant a+b+c+2=2019+2=2021
$$

3 points.

Consider the following marking scheme:

$$
210|210| 210|\underbrace{2200|2200| 2200 \ldots 2200}_{502 \text { blocks of } 2200}| 22 \mid 0000 \ldots
$$

Here the $i$-th digit in the sequence denotes the mark of positive integer $i$. For this marking, $S=2021$, and therefore 2021 is the maximum possible value of $S$.

4 points.