Problem 1740

Solution:

Let $A$ be the set of numbers to color red. If $A = \{n, n+1, \ldots, 2n\}$ there are no three of them for which $x+y=z$, since for every $x, y \in A$ with $x \neq y$ we have $x+y > 2n$.

It remains therefore to prove that this is the only possible choice for the set $A$.

We prove the statement by induction on $n$, beginning with the case $n=3$. If, for the sake of contradiction, we had $1 \in A$ then $A$ could not have two consecutive numbers greater than $1$, so necessarily $A = \{1, 2, 4, 6\}$. But, since $2+4=6$, this gives a contradiction. If instead $1 \notin A$ but $2 \in A$, then $A$ would have to contain at least one of the two pairs $\{3, 5\}$ or $\{4, 6\}$, again giving a contradiction with the hypothesis that one cannot have $x+y=z$ with $x, y, z \in A$.

Suppose now that we have proven uniqueness for the number $n$ and let us prove it for $n+1$.

First of all we observe that $A$ must contain at least one of the numbers $2n+1, 2n+2$, since otherwise $A$ would have to contain $n+2$ numbers between $1$ and $2n$, which is excluded by the inductive hypothesis (only $n+1$ numbers between $1$ and $2n$ can belong to $A$).

We also show that $A$ must contain both numbers $2n+1$ and $2n+2$: if this were not the case, $A$ would have to contain at least $n+1$ of the numbers $\{1, \ldots, 2n\}$ and, by the inductive hypothesis, would have to contain $\{n, n+1, \ldots, 2n\}$. But this would mean that $A$ contains neither $n+(n+1)=2n+1$ nor $n+(n+2)=2n+2$, a contradiction.

At this point, since $2n+1 \in A$, $A$ can contain only one of the numbers from the pairs $\{1, 2n\}, \{2, 2n-1\}, \ldots, \{n, n+1\}$. One sees immediately that $1 \notin A$ since $1+(2n+1)=2n+2$, and therefore $2n \in A$. Similarly, $2 \notin A$, since $2+2n \in A$ and therefore $2n-1 \in A$. Inductively, for every $(a, b)$ with $a+b=2n+1$, the larger of the elements of the pair must necessarily belong to $A$, and therefore $A = \{n+1, n+2, \ldots, 2n+2\}$.