Bariz - Problem

Source: 8th European Mathematical Cup, Junior Category, Q1

Tags: number theory, combinatorics

ThE-dArK-lOrD

26.12.2019 20:19

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.$$Let $S$ denote the sum of marks of the first $2019$ positive integers. Determine the maximum possible value of $S$. Proposed by Ivan Novak

We claim the answer is 2021. It can be achieved: 2200|210|210|...|210|22 where the number of 210 is 671. Let the number of 2, 1, 0 be respectively $x_1, x_2, x_3$. We know $x_1+x_2+x_3=2019$ and we want to prove $2x_1+x_2 <=2021$. Therefore it's sufficent to prove $x_1-x_3<=2$. Indeed, for every positive integer j ∈ {1,...,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 $x_3$.The conclusion follows