Can two (or all three) of x,y,z be the same? I think that has to be true, otherwise, you can permute each working triple in 6 ways, but 6 doesn't divide 2007, which makes the problem trivial.

no x, y and z can't be the same. The sets are ordered, so you can't permute them.

What do you mean by ordered triple? Is triple $ 1,2,3$ considered to be the same as $ 3,2,1$ or different?

they are different

Another derivation of the equation $ 2007 = r^2 - rb + b^2$ using generating functions was just posted at http://www.artofproblemsolving.com/Forum/viewtopic.php?t=274884.

Disappointing for a C3...

Let $B,R$ partition $S$ such that $B$ contains only the blue elements and $R$ contains the red. Since $S$ forms a complete residue set $\mod n,$ for any ordered pair $(x,y)\in S^2$ there exists a unique $z\in S$ such that $n\mid x+y+z.$ Now we count the number of triples such that, WLOG $x\in B$ and $y,z\in R$ since the other cases are similar. If $|B|=x,$ trivially there are $x(n-x)$ such triples. We multiply by $3$ to account for permutations, and thus the problem reduces to solving $n^2-3x(n-x)=2007.$ Taking $\mod 3$ we have $3\mid n$ so let $n=3n'\implies 3n'^2-x(3n'-x)=669.$ $\mod 3$ again we have $x=3x'$ so $n'^2-x'n'+x'^2=223.$ Now since $n'\geq x,$ we have $n'^2-n'x'+x'^2=n'(n'-x')=223-x'^2$ so $x'\leq 14$ and checking cases we get $n'=23,28$ so $\boxed{n=69,84}$ are the only solutions. $\blacksquare$

tfw you can't do simple double counting but generating functions are OP IMO ShortList 2007 C3 wrote: 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 $ \left(x, y, z\right)$ such that: (i) the numbers $ x$, $ y$, $ z$ are of the same color, and (ii) the number $ x + y + z$ is divisible by $ n$. Author: Gerhard Wöginger, Netherlands Answer: $\boxed{n \in \{69, 84\}}$. Let $f$ be any formal series with complex coefficients and $g$ be an operator so that $$g(f)=\frac{1}{n} \left( \sum^{n-1}_{j=0} f(\varepsilon^j) \right),$$where $\varepsilon$ is a primitive $n$-th root of unity. Let $R, B$ be formal series defined by $$R(x) \overset{\text{def}}{:=} \sum_{j \, \text{is red} } x^j$$and $$B(x) \overset{\text{def}}{:=} \sum_{j \, \text{is blue}} x^j,$$for any fixed red-blue coloring of $\{1, 2, \dots, n\}$. Set $F(x)=R(x)+B(x)=x \left(\tfrac{x^n-1}{x-1}\right)$. Note that the desired number of triples is precisely equal to $$g\left(R^3+B^3\right)=g\left(F(F^2-3RB)\right)=g(F^3)-3g(FRB)=n^2-3r(n-r)=2007,$$since for any $x $ red and $y$ blue, there is a unique $z \le n$ for which $n \mid x+y+z$. Solving this for $r \le n$ yields $n \in \{69, 84\}$ just as we remarked initially. $\blacksquare$

jgnr wrote:

Why isn't the number of bichromatic divisible triplets $6rb$ ?We should have six permutation of $(x,y,z)$ .

We claim that $\boxed{n \in \{69, 84\}}$. Let the red numbers be $r_1, r_2, \ldots, r_k$, and the blue numbers be $b_1, b_2, \ldots, b_{n - k}$. Now, note that the coefficient of $x^i$ in the generating function \begin{align*} P(x) &= \left(\sum_{i = 1}^k x^{r_i}\right)^3 + \left(\sum_{i = 1}^{n - k} x^{b_i}\right)^3 \end{align*}is the number of ordered triples $(x, y, z)$ such that $x + y + z = i$ and $x, y, z$ have the same color. By the roots of unity filter, the sum of the coefficients of $x^{kn}$, as $k$ ranges across the positive integers (note that $P$ has constant term $0$), is \begin{align*} S &= \frac{\sum_{i = 0}^{n - 1} P\left(\omega^n\right)}{n}, \end{align*}where $\omega = e^{\frac{2\pi i}{n}}$. We claim that $P\left(\omega^q\right) = 0$ for $q > 0$. Indeed, note that $x + x^2 + \cdots + x^n$ is a factor of $P(x)$. If $q > 0$, and $\gcd(q, n) = d$, \begin{align*} \omega + \omega^2 + \cdots + \omega^n &= \frac{n}{d}\left(\sum_{i = 0}^{d - 1} \omega^i\right) \\ &= 0. \end{align*}Hence, $0 \mid P\left(\omega^q\right)$ for $q > 0$, meaning that $P\left(\omega^q\right) = 0$. Therefore, \begin{align*} S &= \frac{P(1)}{n}. \end{align*} We are given that $S = 2007$. Thus, we have \begin{align*} \frac{k^3 + (n - k)^3}{n} &= 2007 \\ n^2 - 3kn + 3k^2 &= 2007. \end{align*}Note that $k, n$ are positive integers. This is a quadratic in $n$. Since $n$ is an integer, its discriminant must be a perfect square, meaning that \begin{align*} 4\cdot 2007 - 3k^2 &= t^2 \end{align*}for some nonnegative integer $t$. Hence, we have $t^2 + 3k^2 = 4 \cdot 2007$. By taking mod $3$, we find that both $t, k$ are divisible by $3$. Hence, write $t = 3u$ and $k = 3v$. The equation reduces to $u^2 + 3v^2 = 223 \cdot 4$. By exhaustive search, one may find that the positive integer pairs $(u, v)$ satisfying this equation are $(28, 6), (23, 11)$, implying that $k = 3v = 18, 33$. Solving the initial quadratic in $n$ then yields $n = 69, 84$ when $k = 18, 33$ respectively. Thus, $\boxed{n \in \{69, 84\}}$, as claimed. $\Box$

The answer is $69$ and $84$. Assume there are $k$ red numbers and thus $n-k$ blue numbers. Say a triple $(x,y,z)$ is vanishing if $x+y+z$ is divisible by $n$. Claim: The number of vanishing $(x,y,z)$ containing both red and blue numbers is $3k(n-k)$. Proof. The key is to count the number of vanishing triples with $x$ and $y$ different colors. Note that $x$ and $y$ uniquely determine $z$, so there are $2k(n-k)$ such triples. Similarly the number of vanishing triples with $y$ and $z$ different colors is $2k(n-k)$, and the number of vanishing triples with $z$ and $x$ different colors is $2k(n-k)$. For each such vanishing triple, among $(x,y)$, $(y,z)$, $(z,x)$ exactly two pairs have numbers with different colors, so double counting gives $3k(n-k)$ such vanishing triples. $\blacksquare$ Hence $2007=n^2-3k(n-k)$. Since $3\mid n$, let $n=3m$ for some $m$; then $669=3m^2-k(3m-k)$. Since $3\mid k$, let $k=3s$ for some $s$; then $223=m^2-3ms+3s^2$. The polynomial $3s^2-3m\cdot s+(m^2-223)$ in $s$ has perfect square discriminant $\Delta=2676-3m^2$. Since $3\mid\Delta$, let $\Delta=9t^2$. Then $892=m^2+3t^2$, and an exhaustive check gives $m\in\{23,28\}$, so $n\in\{69,84\}$, as desired.

The answers are $69$ and $84$. We claim that if there are $a$ red numbers and $b$ blue numbers, there are exactly $a^2-ab+b^2$ monochromatic triplets divisible by $n$. To do this, we use roots of unity filter. If we define $P(x)=\sum_{i\in R}x^i$, $Q(x)=\sum_{j\in B}x^j$, we want $\frac{1}{n}\sum_{i=0}^{n-1}P(\zeta^i)^3+Q(\zeta^i)^3$. However, $P+Q=\sum_{i=0}^{n-1}x^i$ divides $P(x)^3+Q(x)^3$, and it vanishes when $i\neq 0$. So, our equation becomes $\frac{1}{n}(P(1)^3+Q(1)^3)=\frac{a^3+b^3}{n}=a^2-ab+b^2$, as desired. To finish, we use quadratic formula to solve for $a$. Note that we need $b^2+4(2007-b^2)=8028-3b^2$ to be a perfect square, which is a finite case check. Checking, we see that only $b=18, 33, 51$ work, which yield $(a,b)=(18,51), (33, 51), (51, 18), (51,33)$.

Solved with nukelauncher. Define generating functions for the red and blue numbers: polynomials $R(x),B(x)$ defined as $R(x)=\sum_{i \text{ red}}x^i$ and $B(x)=\sum_{i \text{ blue}}x^i$. So $R(x)+B(x)=x+\cdots+x^n=\tfrac{x(x^n-1)}{x-1}$. With $\omega$ being a primitive $n$th root of unity, roots of unity filter tells us that \[[R(\omega)^3 + \cdots + R(\omega^n)^3] + [B(\omega)^3+\cdots + B(\omega^n)^3] = 2007n.\]However, we also have \begin{align*} \sum_{k=1}^n R(\omega^k)^3+\sum_{k=1}^n B(\omega^k)^3&=\sum_{k=1}^{n-1}\left[R(\omega^k)^3+B(\omega^k)^3\right]+(R(1)^3+B(1)^3)\\ &=\left[0+\dots+0\right] + R(1)^3+B(1)^3\\ &=2007n. \end{align*}Therefore, \[R(1)^3+B(1)^3=2007n, \quad R(1)+B(1)=n.\]This gives \[R(1)^2-nR(1)+\tfrac{n^2-2007}{3}=0.\]Since $R(1)$ is an integer, the discriminant is a perfect square. Thus, for some integer $k$, we have \[k^2=n^2-\tfrac43(n^2-2007)=2676-\tfrac13n^2.\]This finally becomes \[n^2+3k^2=8028.\]We must have $3\mid n$, so let $n=3m$. Then $3m^2+k^2=2676$, which gives $3\mid k$ so let $k=3\ell$. This means $m^2+3\ell^2=892$. If suffices to test $\ell=1,\ldots,17$. We get $\ell=6,11,17$ which correspond to $n=84,69,15$. It remains to check if $0\le R(1)\le n$ for these choices of $n$. For $n=15$, the solutions to the quadratic are $R(1)=-18,33$. These do not work. For $n=69$, the solutions are $R(1)=18,51$, which work. For $n=84$, the solutions are $R(1)=54,33$, which work. All cases checked, we conclude that the answer is $n=\boxed{69,84}$.

Imagine forgetting roots of unity filter existed for the entirety of the problem. (Well now you have a solution without it.) Let $C$ be a coloring of $S$, and let $N$ be the number of ordered triples $(x,y,z)$ satisfying the conditions in the problem. We would like all $n$ where $N=2007$. First, notice that $3|N$ and all triples that aren't all the same number have a multiple of three number of permutations, so the number of working triples that are the same number is a multiple of 3. Thus $3|n$. Claim: Suppose that a coloring $C$ has $x$ red and $y$ blue numbers, where $x\le y$. Then changing the color of a number $i$ from red to blue increases $N$ by $3(y-x+1)$. Proof. Label all blue numbers as $+3$ and label all red numbers other than $i$ as $-3$. We claim that $N$ will change by the sum of all labels, which would prove the claim. Notice that for all $j\in S$, there is exactly one $k\in S$ such that $i+j+k$ is a multiple of $n$. Now consider locally: 1. If $j,k$ are red and $n|(i+j+k)$, then we lose six ordered pairs (permutations). The sum of the two labels is $-6$ and corresponds with this. Similarly, if $j,k$ are blue and $n|(i+j+k)$, we gain six ordered pairs, and the sum of the labels of $j$ and $k$ correspond for that. 2. If $j$ is red and $n|(i+2j)$ or $n|(2i+j)|$, then we lose three ordered pairs (permutations). The label of $j$ (-3) corresponds with this. Similarly, if $j$ is blue and we gain three ordered pairs, the label for $j$ corresponds with this. 3. If one of $j,k$ is red and the other is blue, with $n|(i+j+k)$, then there is no change. The sum of the labels of $j$ and $k$ (0) correspond with this. Since every $j\in S$ except for $i$ has exactly one $k\in S$ with $n|(i+j+k)$, every $j\in S$ except $i$ falls into exactly one of these three cases. Therefore the claim is proved. $\blacksquare$ Notice that there are a total of $n^2$ ordered triples (take the first two values arbitrarily and the third is fixed), when all numbers are the same color we have $N=n^2$. Therefore, by moving elements one by one to the other color we find that $N$ is only dependent on the number of numbers of each color. Moreover, one can check that: 1. When $n$ is a multiple of $6$, if the color with more numbers has $\frac{n}{2}+k$ numbers, $N=\frac{n^2}{4}+3k^2$; 2. When $n$ is $3$ modulo $6$, if the color with more numbers has $\frac{n+1}{2}+k$ numbers, $N=\frac{n^2+3}{4}+3k(k+1)$; by showing that the claim holds in these cases and that when every number is the same color, $N=n^2$. Now let's get the answer. When $n$ is a multiple of $6$, since our desired $N$ is a multiple of $9$, $k$ must be a multiple of $3$. Letting $n=6n'$ and $k=3k'$ and dividing both sides by $9$ gives us that we would like to solve $$n'^2+3k'^2= 223.$$Checking gives the only solution in this case to be $n'=14, k'=3 \Rightarrow n=84$. When $n$ is $3$ modulo $6$, letting $n=6n'+3$ and dividing both sides by $3$ gives us $$3n'^2+3n'+k(k+1)=668.$$Checking gives the solutions to be $n'=11, k=16$, giving us $n=69$, and $n'=2, k=25$ (which gives us a contradiction as we must have $k\le \frac{n}{2})$. Therefore the answer is $n=69, 84$. The construction is given by the $k$-value (giving us how many numbers should be red and how many should be blue).

The answer is $n=69,84$. First note that if $3 \nmid n$, there is exactly one valid pair—$(n, n, n)$—with all three values equal. If at least two values differ, then we can cyclically permute $(a,b,c)$ to $(b,c,a)$ and $(c,a,b)$. Thus if $3 \nmid n$, the number of working triples is $1 \pmod{3}$. Since $3 \mid 2007$, we have $3 \mid n$. We now use a roots of unity filter to solve the problem. Let $R, B$ denote the red and blue colored elements of $S$ respectively; next let $R(x) = \sum_{i \in R} x^i$ and define $B(x)$ similarly. The number of admissible pairs is $$\frac{1}{n}\sum_{i=0}^{n-1} (R(z^i)^3+B(z^i)^3),$$where $z$ is a primitive $n$-th root of unity. Since $R(x) + B(x) \mid R(x)^3 + B(x)^3$, and $R(zi) + B(zi)$ vanishes if $i \neq 0$, it follows that the above expression is simply equal to $\tfrac{R(1)^3+B(1)^3}{n}=R(1)^2-R(1)B(1)+B(1)^2$. Since $R(1) = |R|$ and $B(1) = |B|$, the problem is reduced to finding all $n$ such that there exist $x,y$ with $x+y=n$ and $x^2-xy+y^2=2007$. WLOG, let $x>y$, and define $x-y=m>0$, so the equation becomes $3m^2+n^2=8028$, and we’re looking for possible values of $n$. We evidently require $3 \mid n$, so the equation becomes $m^2 + 3N^2 = 2676$ where $n=3N$; then $3 \mid m$, and the equation becomes $3M^2 + N^2 = 892$, where $m = 3M$. From here, a manual case check gives the solutions to be $(M,N) = (17,5),(11,23),(6,28)$. But since $N > M$, we must discard the first solution, which gives $N \in \{23, 28\} \implies n \in \{69, 84\}$ as desired. Construction is obvious. $\blacksquare$

Let $A$ be the set of red numbers, and $B$ be the set of blue numbers. We count the number of triples that are not of same color. Note that for each $(x,y)\in A\times B$, there is a unique value $z\in S$ such that $n\mid x+y+z$. Therefore, there are $|A|\cdot |B|$ triples in the form $(A,B,A)$ or $(A,B,B)$. Similarly, there are $|A|\cdot |B|$ triples in the form $(A,A,B)$ and $(A,B,B)$ and the same amount of triples in the form $(A,A,B)$ and $(B,A,B)$. If we flip each of the colors in the previous result, we get that there are $6|A|\cdot |B|$ triples, but we count each case twice, so the complement of what we want is $3|A|\cdot |B|$. Thus, \[2007= n^2-3|A||B|\]From here, it is easy to see that $n=69$ or $84$ are the only ones to work.

Let $R$ and $B$ be the integers colored red and blue respectively. Define \begin{align*} r(x) &= \sum_{r \in R} x^r \\ b(x) &= \sum_{b \in B} x^b \\ \end{align*}so $r(x) + b(x) = \frac{x^{n+1} - 1}{x - 1} - 1$. Let $\omega$ be a primitive $n$th root of unity. Then it follows that \[ \sum_{i=1}^n r^3(\omega^i) + b^3(\omega^i) = 2007n. \]Note that $r(\omega^i) + b(\omega^i)$ is $0$ whenever $i \ne n$. As such, this just simplifies as \[ r^3(1) + b^3(1) = 2007n. \]If $|R| = d$, then this is just \[ d^3 + (n - d)^3 = 2007n. \]which if we let $e = n - d$ simplifies as \[ d^2 - de + e^2 = 2007 \]of which we take $\pmod{3}$. By looking $\pmod{3}$ this is equivalent to the number of solutions to \[ d^2 - de + e^2 = 223 \]It follows that the discriminant \[ 892 - 3e^2 = t^2 \]is a perfect square. We can then exhaustively search to get that $e$ is either $6$ or $11$, which gives that $d$ is $17$, so the answers are $\boxed{69}$ and $\boxed{84}$ respectively.

Genfunc it. Let $g(x)$ be some genfunc thingy composed of the sum of some of the exponents $\{x^1, x^2, \cdots x^n\}$, representing the blue elements. WLOG that $x^n$ is not in $g(x)$. Okay now we let function $f(x) = (g(x))^3 + ((x^1+x^2+\cdots x^n) - g(x))^3$, this creates a bunch of terms where the exponent of $x$ represents the sum of the three elements we choose in the triple. Now we use RoUF to find the terms with exponent divisible by $n$: (let $\omega$ be the primitive $n$th root of unity) \begin{align*} \text{answer} &= \frac1n \sum_{i = 0}^{n-1} f(\omega^i)\\ &= \frac1n \left(f(1) + \sum_{i = 1}^{n-1} f(\omega^i)\right)\\ &= \frac1n \left(g(1)^3 + (n-g(1))^3 + \sum_{i = 1}^{n-1} (g(\omega^i)^3 + (0-g(\omega^i))^3)\right)\\ &= \frac1n \left(g(1)^3 + (n-g(1))^3 + 0\right)\\ &= 2007, \end{align*} so we want to find $n$ such that $x^3 + (n-x)^3 = 2007n$ has a solution $x\in [0, n-1]$. So $$n^2 - 3nx + 3x^2 = 2007 \implies x = \frac{3n \pm \sqrt{(3n)^2 -12(n^2-2007)}}{6}$$ Thus we must have $2007\cdot 12 -3n^2 = m^2$ a perfect square. Noticing that $27 \mid 2007\cdot12$, we must have $3 \mid n, 9\mid m \implies n = 3k_1, m = 9k_2 \implies k_1^2 + 3k_2^2 = 892$. A simple trial and error now leaves us with only three possiblities: $n = 15, 69, 84$. It can be verified that $n=15$ does not give us an $x$ in the desired range, and furthermore that $69$ and $84$ both work, hence the answer is $\boxed{n \in\{69, 84\}}$. Done

Curious_Droid wrote: Genfunc it You made my day

The answer is $69,84$. Suppose for a certain coloring there are $b$ blue numbers and $r$ red numbers. Now we count the number of triples $(x,y,z)$ that aren't all of the same color (as in they are two of one color and one of the other) and $n\mid x + y + z$. First we count the number of such triples when $x,y$ have different colors. There are in total $2 \cdot br$ ways to choose $x,y$. Notice that there is a unique $z$ with $n\mid x + y+ z$, and $(x,y,z)$ must have two of one color and one of the other. Therefore, there are $2br $ ways to choose $x,y,z$ in this case. If $y,z$ are of different colors, or if $x,z$ are of different colors, we similarly also have $2br$ ways. However, each triple has exactly two of $\{x,y\} , \{y,z\}, \{x,z\}$ having two different colors, which means that there are totally $\frac{2br + 2br + 2br}{2} = 3br $ ways to choose $(x,y,z)$ not all of the same color with $n\mid x+ y + z$. There are $n^2$ ways to choose $x,y,z\in S$ with $n\mid x + y+ z$ because each $(x,y)$ admits exactly one possibility for $z$. Thus, there are $n^2 - 3br = r^2 - rb + b^2$ desired triples, so $r^2 - rb + b^2 = 2007$. The problem is equivalent to there existing positive integers $r+b= n$ with $r^2 - rb + b^2 = 2007$. Considering $(r,b) = (51,18)$ and $(51,33)$, we see that $n = 69,84$ work. Now we prove that $n\in \{69,84\}$. Now, we clearly have $3\mid n$, otherwise the number of triples couldn't be a multiple of $3$. Claim: $3\mid r$ and $3\mid b$. Proof: Suppose not. Then, $\frac{r^3 + b^3}{r + b} = 2007$, so $\nu_3(r^3 + b^3) - \nu_3(r + b) = 2 $. However, since $3\mid r + b$ but not $r$ or $b$, by LTE, we have $\nu_3(r^3 + b^3) = \nu_3(r + b) + 1$, contradiction. $\square$ Now, if $r = 3x$ and $b = 3y$, we have $x^2 - xy + y^2 = 223$, so $(x-y)^2 + xy = 223$. WLOG assume that $x \ge y$. So then $0\le x - y \le 14$. It is now casebash time. We claim that $x - y\in \{6,11\}$. If $x - y =0$, then $x^2 = 223$, absurd. If $x - y = 1$, then $xy = 222$, so $x - y \ge 37 - 6 = 31$. If $x - y = 2$, then $xy = 219$, so $x - y \ge 73 - 3 = 70$. If $x - y = 3$, then $xy = 214$, so $x - y \ge 107 - 2 \ge 105$. If $x - y = 4$, then $xy = 207$, so $x - y \ge 23 - 9 = 14$. If $x - y = 5$, then $xy = 198$, so $ x - y \ge 18 - 11 = 7$. If $x - y = 7$, then $xy = 174$, so $x - y \ge 29 - 6 = 23$. If $x - y = 8$, then $xy = 159$, so $x - y \ge 53 - 3 = 50$. If $x - y = 9$, then $xy = 142$, so $x - y \ge 71 - 2 = 69$. If $x - y = 10$, then $xy = 123$, so $x - y \ge 41 - 3 = 38$. If $x - y = 12$, then $x y = 79$, so $x - y \ge 79 - 1 = 78$. If $x - y = 13$, then $xy = 54$, so $x - y \in \{53,25,3\}$. If $x - y = 14$, then $xy = 27$, so $x - y$ is equal to $26$ or $6$. Therefore, we must have $x - y = 6$ or $x - y = 11$. If $x - y = 6$, then $xy = 187\implies x = 17, y = 11$, so $n = 3(x + y) = 84$. If $x - y = 11$, then $xy = 102\implies x = 17, y = 6$, so $n = 3(x + y) = 69$. Thus, we must have $n\in \{69,84\}$, as desired.

$ $