Let $n>2$ be an integer$.$ We want to color in red exactly $n+1$ of the numbers $1,2,\cdots,2n-1, 2n$ so that there do not exists three distinct red integers $x,y,z$ satisfying $x+y=z.$ Prove that there is one and one only way to color the red numbers according to the given condition$.$
Problem
Source: ITAMO 2019 #3
Tags: combinatorics, ITAMO 2019
JengaBetterThanLego
03.05.2019 21:05
Colour the numbers $n,n+1,n+2...2n-1,2n$ red. The smallest sum of two red numbers is $n+n+1 = 2n+1$ and the largest red number is $2n$. Therefore, this colouring works.
Will update with the second part once/if I get it.
Pathological
04.05.2019 05:17
Suppose that there were some other way to color $n+1$ numbers red so that the condition is satisfied, so that some number $< n$ is red.
Let $d$ be the largest chosen integer. If $d$ is odd, then there are at most $1 + \frac{d-1}{2} \le n$ red numbers, since at most one of the numbers in each of the pairs $(1, d-1), (2, d-2), \cdots, (\frac{d-1}{2}, \frac{d+1}{2})$ can be red. If $d$ is even and less than $2n$, then there are at most $1 + \frac{d-2}{2} + 1 \le n$ red numbers, since at most one of the numbers in each of the pairs $(1, d-1), \cdots, (\frac{d}{2} - 1, \frac{d}{2} + 1)$ can be red. Hence, we conclude that $d = 2n$. Furthermore, since there are at most one of the numbers in each of the pairs $(1, 2n-1), (2, 2n-2), \cdots, (n-1, n+1),$ we know that $n$ must be red and each of these pairs has exactly one red number. Therefore, in the event that some $i < n$ was red, we'd have that $i+n$ is not red (as $n$ is red), from which we get $2n-(i+n) = n-i$ is red. But then $i + (n-i) = n$ violates the condition, giving that we must have all red numbers $\ge n$, contradicting our assumption.
Hence, our initial assumption was incorrect, and there is only one way to color the red numbers.