48th International Mathematical Olympiad Vietnam 2007 Shortlisted Problems with Solutions

Suppose that the numbers $1,2,\dots ,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-rb+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\ne 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-3rb=(r+b{)}^2-3rb=r^2-rb+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-rb+b^2=2007$. Therefore, $9\mid r^2-rb+b^2=(r+b{)}^2-3rb$. From this it consequently follows that $3|r+b,3|rb$, and then $3|r,3|b$. Set $r=3s,b=3c$. We can assume that $s\ge c$. We have $s^2-sc+c^2=223$.

Furthermore, $$892=4\left(s^2-sc+c^2\right)=(2c-s{)}^2+3s^2\ge 3s^2\ge 3s^2-3c(s-c)=3\left(s^2-sc+c^2\right)=669$$ so $297\ge s^2\ge 223$ and $17\ge s\ge 15$. If $s=15$ then $$c(15-c)=c(s-c)=s^2-\left(s^2-sc+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$.