SAUDI ARABIAN IMO Booklet 2023

The smallest such number is $n=9$. Suppose that $n$ is a number allowing for coloring with the desired properties. Then $n\ge 2$ since each color needs to be used at least once. Note that $n$ cannot be blue since it is inexpressible as a difference of two numbers between $1$ and $n$, therefore $n$ is red. On the other hand, $1$ and $2$ cannot be red, since none of them is a sum of two distinct positive integers, which means $1$ and $2$ are blue (and in particular $n\ge 3$). Now $n-1$ cannot be a difference of two red numbers (since $1$ is blue), so $n-1$ is red. Similarly $n-2=(n-1)-1$ has to be red since both $1$ and $2$ are blue. It follows that $n\ge 5$.

Since $n$ is red, it needs to be a sum of two distinct blue numbers. But a sum of two blue numbers cannot exceed $$(n-3)+(n-4)=2n-7.$$ Therefore, $2n-7\ge n⟹n\ge 7$. If $n=7$, then the only remaining possibility to express $7$ as a sum of two blue numbers is $3+4$, but then $4$ is not a difference of two red numbers, contradiction. Similarly with $n=8$. We have proved that $n\ge 9$. It remains to show that there exists a valid coloring for $n=9$. We can color $1$, $2$, $4$, $5$, $6$ blue and $3$, $7$, $8$, $9$ red. Correctness of this coloring follows from the simple arithmetic: $$1=9-8,2=9-7,4=7-3,5=8-3,6=9-3,$$ $$3=1+2,7=1+6,8=2+6,9=4+5.$$