C3. Find all positive integers $n$, for which the numbers in the set $S=\{1,2, \ldots, n\}$ can be colored red and blue, with the following condition being satisfied: the set $S \times S \times S$ contains exactly 2007 ordered triples $(x, y, z)$ such that (i) $x, y, z$ are of the same color and (ii) $x+y+z$ is divisible by $n$.
Answer. $n=69$ and $n=84$.
Solution. 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 $\left(x, y, z_{x, y}\right)$ 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,
$$
\begin{array}{l}
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 \\
\text { so } 297 \geq s^{2} \geq 223 \text { and } 17 \geq s \geq 15 \text {. If } s=15 \text { then } \\
\qquad c(15-c)=c(s-c)=s^{2}-\left(s^{2}-s c+c^{2}\right)=15^{2}-223=2
\end{array}
$$
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$.
Comment. After the formula for the number of monochromatic divisible triples is found, the solution can be finished in various ways. The one presented is aimed to decrease the number of considered cases.