IMO Shortlist, 2007

Suppose that the numbers $1,2, \ldots, n$ are colored red and blue. Denote by $R$ and $B$ the sets of red and blue numbers, respectively; let $|R|=r$ and $|B|=b=n-r$. Call a triple $(x, y, z) \in S \times S \times S$ monochromatic if $x, y, z$ have the same color, and bichromatic otherwise. Call a triple $(x, y, z)$ divisible if $x+y+z$ is divisible by $n$. We claim that there are exactly $r^{2}-r b+b^{2}$ divisible monochromatic triples.

For any pair $(x, y) \in S \times S$ there exists a unique $z_{x, y} \in S$ such that the triple $(x, y, z_{x, y})$ is divisible; so there are exactly $n^{2}$ divisible triples. Furthermore, if a divisible triple $(x, y, z)$ is bichromatic, then among $x, y, z$ there are either one blue and two red numbers, or vice versa. In both cases, exactly one of the pairs $(x, y),(y, z)$ and $(z, x)$ belongs to the set $R \times B$. Assign such pair to the triple $(x, y, z)$.

Conversely, consider any pair $(x, y) \in R \times B$, and denote $z=z_{x, y}$. Since $x \neq y$, the triples $(x, y, z),(y, z, x)$ and $(z, x, y)$ are distinct, and $(x, y)$ is assigned to each of them. On the other hand, if $(x, y)$ is assigned to some triple, then this triple is clearly one of those mentioned above. So each pair in $R \times B$ is assigned exactly three times.

Thus, the number of bichromatic divisible triples is three times the number of elements in $R \times B$, and the number of monochromatic ones is $n^{2}-3 r b=(r+b)^{2}-3 r b=r^{2}-r b+b^{2}$, as claimed.

So, to find all values of $n$ for which the desired coloring is possible, we have to find all $n$, for which there exists a decomposition $n=r+b$ with $r^{2}-r b+b^{2}=2007$. Therefore, $9 \mid r^{2}-r b+b^{2}=(r+b)^{2}-3 r b$. From this it consequently follows that $3|r+b, 3| r b$, and then $3|r, 3| b$. Set $r=3 s, b=3 c$. We can assume that $s \geq c$. We have $s^{2}-s c+c^{2}=223$.

Furthermore,
$$892=4\left(s^{2}-s c+c^{2}\right)=(2 c-s)^{2}+3 s^{2} \geq 3 s^{2} \geq 3 s^{2}-3 c(s-c)=3\left(s^{2}-s c+c^{2}\right)=669$$
so $297 \geq s^{2} \geq 223$ and $17 \geq s \geq 15$. If $s=15$ then
$$c(15-c)=c(s-c)=s^{2}-\left(s^{2}-s c+c^{2}\right)=15^{2}-223=2$$
which is impossible for an integer $c$. In a similar way, if $s=16$ then $c(16-c)=33$, which is also impossible. Finally, if $s=17$ then $c(17-c)=66$, and the solutions are $c=6$ and $c=11$. Hence, $(r, b)=(51,18)$ or $(r, b)=(51,33)$, and the possible values of $n$ are $n=51+18=69$ and $n=51+33=84$.