Junior Balkan Mathematical Olympiad 2021 - Problem 4 | Solution - 2 July 2021



Problem 4. Let $M$ be a subset of the set of $2021$ integers $\{1, 2, 3, ..., 2021\}$ such that for any three elements (not necessarily distinct) $a, b, c$ of $M$ we have $\|a + b - c \| > 10$ . Determine the largest possible number of elements of $M$ .

Solution 1 An example with $1006$ integers is $M = \{1016,1017,\ldots,2021\}$ which works since $a+b-c \geq 1016 + 1016 - 2021 = 11$ for any $a,b,c \in M$ . Now suppose there is $M$ with the given property and at least $1007$ elements. Note that there are at least $1006$ negative integers of the form $a-b$ for distinct $a,b\in M$ - indeed, if the elements of $M$ are $x_1 < x_2 < \ldots < x_{1007} < \ldots$ then $x_i - x_{1007}$ , $i=1,\ldots,1006$ are such. Colour these differences in blue. Also, colour each element of $-M$ (i.e. the integers $-x_1, -x_2,\ldots, -x_{1007}, \ldots$ ) in red. Now there are two cases: - If there is an integer which is both red and blue, then $a - b = -x_i$ for some $a,b,x_i \in M$ and so we have $a,b,c \in M$ which $a+b-c = 0$ , which contradicts the hypothesis. - Otherwise, no integer is both red and blue and since all coloured integers (which are at least $2013$ in total) are between $(-2020)$ and $(-1)$ , it follows that there is a difference of a red and a blue integer equal to $m\leq 10$ and we get a contradiction as in the previous case (but with $0$ replaced by $m$ ). Solution 2 An example with $1006$ integers is $M = \{1016,1017,\ldots,2021\}$ which works since $a+b-c \geq 1016 + 1016 - 2021 = 11$ for a ny $a,b,c \in M$ . Further assume that $M$ has (at least) $1007$ elements and let $A$ denote the given set. Let $a_{1}<a_{2}<\dots<a_{1007}$ be the elements of $M$ . Consider the following set (it's easy to check that it's well-defined and also a subset of $A$ ) $M'=\left\{a_{1007}-a_{1006}, a_{1007}-a_{1005},\dots, a_{1007}-a_{1}, a_{1007}-a_{1}+1, a_{1007}-a_{1}+2,\dots, a_{1007}-a_{1}+10\right\}.$ By the problem's condition, $M$ and $M'$ must be disjoint. But since $\|M\|+\|M'\|=1007+1016=2023>\|A\|=2021$ and $M, M'\subset A, M\cap M'=\emptyset$ , we get a contradiction. This ends our proof.;