Consider the set $ M = \{1,2, \ldots
,2008\}$. Paint every number in the set $ M$ with one of the three
colors blue, yellow, red such that each color is utilized to paint
at least one number. Define two sets:
$$ S_1=\{(x,y,z)\in M^3 \mid x,y,z\; {\rm have\; the\; same\; color\; and\;
}2008 | (x + y + z)\}$$ $$ S_2=\{(x,y,z)\in M^3 \mid x,y,z\;{\rm
have\; pairwisely\; different\; colors\; and\; }2008 | (x + y + z)\}$$
Prove that $ 2|S_1| > |S_2|$ (where $ |X|$ denotes the number of
elements in a set $ X$).
(Online) Solution: The residue (I mean zero here!) is
just meaningless.In other words,one can prove the same comparation
for $ x+y+z=d(\pmod n)$ (I put $ 2008=n$ for generality) So assume
three generating functions: $$ A(x) = \sum_{a\ is \ red}x^{a –
d/3}$$ $$ B(x) = \sum_{b\ is\ blue}x^{b – d/3}$$ and $$ C(x) =
\sum_{c \ is\ yellow}x^{c – d/3}$$ So all we need to prove is as
follows: $$ 2\times \frac {1}{n}(\sum_{x|x^n = 1}A(x)^3 + B(x)^3 +
C(x)^3) > \frac {6}{n}(\sum_{x|x^n = 1}A(x)\times B(x)\times
C(x))$$ It follows directly from CS inequality (easily
to check that the equality won't occur)!
Now my question here is: How can they apply CS if there are not even a real numbers?
Best Answer
I don't think application of C-S is the right approach, at least not directly. However, note the following (I changed your variable from $x$ to $t$ since I feel $x$ is used for two different meanings): $$A(t)+B(t)+C(t)=t^{-d/3}\sum_{k\in M}t^k.$$ If we replace $t$ by $\zeta_l=e^{\frac{2\pi i l}{n}}$, then it follows that $$A(\zeta_l)+B(\zeta_l)+C(\zeta_l)=0$$ for $l=1,2,\ldots,n-1$ (recalling that $M=\{1,2,\ldots,n\}$). From the identity $$p^3+q^3+r^3-3pqr=(p+q+r)(p^2+q^2+r^2-qr-rp-pq),$$ it follows that $p^3+q^3+r^3=3pqr$ if $p+q+r=0$, and so $$\big(A(\zeta_l)\big)^3+\big(B(\zeta_l)\big)^3+\big(C(\zeta_l)\big)^3=3\cdot A(\zeta_l)\cdot B(\zeta_l)\cdot C(\zeta_l).$$ On the other hand, $$\big(A(\zeta_0)\big)^3+\big(B(\zeta_0)\big)^3+\big(C(\zeta_0)\big)^3=\big(A(1)\big)^3+\big(B(1)\big)^3+\big(C(1)\big)^3$$ satisfies $A(1),B(1),C(1)\geq 0$. Therefore, we can apply AM-GM (or C-S) to get $$\big(A(\zeta_0)\big)^3+\big(B(\zeta_0)\big)^3+\big(C(\zeta_0)\big)^3\geq 3\cdot A(1)\cdot B(1)\cdot C(1)=3\cdot A(\zeta_0)\cdot B(\zeta_0)\cdot C(\zeta_0).$$ Therefore, $$\sum_{l=0}^{n-1}\Big(\big(A(\zeta_l)\big)^3+\big(B(\zeta_l)\big)^3+\big(C(\zeta_l)\big)^3\Big)\geq \sum_{l=0}^{n-1}\Big(3\cdot A(\zeta_l)\cdot B(\zeta_l)\cdot C(\zeta_l)\Big),$$ which is equivalent to the required result.
Indeed, it can be shown that \begin{align}2|S_1|-|S_2|&=2\Big(\big(A(1)\big)^2+\big(B(1)\big)^2+\big(C(1)\big)^2-B(1)\cdot C(1)-C(1)\cdot A(1)-A(1)\cdot B(1)\Big)\\&=\big(B(1)-C(1)\big)^2+\big(C(1)-A(1)\big)^2+\big(A(1)-B(1)\big)^2.\end{align}