Let $M=\{1,2,\cdots,n\}$, each element of $M$ is colored in either red, blue or yellow. Set $A=\{(x,y,z)\in M\times M\times M|x+y+z\equiv 0\mod n$, $x,y,z$ are of same color$\},$ $B=\{(x,y,z)\in M\times M\times M|x+y+z\equiv 0\mod n,$ $x,y,z$ are of pairwise distinct color$\}.$ Prove that $2|A|\geq |B|$.
Problem
Source:
Tags: polynomial, inequalities, combinatorics
13.11.2010 13:33
Consider the polynomials $R(x),B(x),Y(x)$ where $R(x)=x^{r_1}+x^{r_2}+...+x^{r_k}$, and $r_i$ are the elements of $M$ that are coloured red, and similar for $B$ and $Y$. Let $\omega$ be the $n^{\text{th}}$ root of unity. For some $k \not \equiv 0 \mod n$ we have $R(\omega^k)+B(\omega^k)+Y(\omega^k) = \omega^k + \omega^{2k} +...+\omega^{nk} = 0 \qquad (1)$. Now each term in $R(x)^3$ represents a triplet from the set of red points, $R$. That is the term $c_kx^k$ says there are $c_k$ red triplets with sum $k$. The same is true for $B(x)^3$ and $Y(x)^3$. On the other hand, $R(x)\cdot B(x)\cdot Y(x)$ gives the number of ordered triplets $(x,y,z)$ with colours red, blue, yellow respectively. From Euler's identity we have. $R(x)^3+B(x)^3 + Y(x)^3 - 3R(x)B(x)Y(x)$ $= \frac{1}{2}\left(R(x)+B(x)+Y(x)\right)\left((R(x)-B(x))^2+(B(x)-Y(x))^2+(Y(x)-R(x))^2\right) \qquad(2)$ Combining (1) and (2) we have $R(\omega^k)^3+B(\omega^k)^3 + Y(\omega^k)^3 = 3R(\omega^k)B(\omega^k)Y(\omega^k)$, when $n\not | k$. When $k=n$ it becomes an inequality because $R(1),B(1),Y(1)\in \mathbb{N}$. Now by the root of unity filter we have $\frac{1}{n}\sum_{k=0}^{n-1} \left( R(\omega^k)^3+B(\omega^k)^3 + Y(\omega^k)^3 - 3R(\omega^k)B(\omega^k)Y(\omega^k)\right) = |A| - 3|B'| \ge 0$ Where $B'$ is only the ordered triplet that we mentioned before. This means each triplet in $B'$ can be permuted in $3!=6$ ways to get a triplet in $B$, so substituting $|B'|=\textstyle\frac{1}{6}|B|$ we get $2|A| \ge |B|$ as desired $\square$ Note: Another interesting fact that follows from this proof is that $k=2|A|-|B|$ depends only on the number of elements we colour red, blue, and yellow and not how we partition them. For example, as long as we have the same number of red, blue and yellow elemenets (no matter how that occurs) we will always get equality $2|A|=|B|$
21.11.2010 09:04
It is vn tst 2008 pro 6 http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1247489&sid=c6ddab093cfa37a59b722edbf21ff938#p1247489
20.08.2015 02:00
Suppose that there are $r, b, y$ elements of $M$ that are colored red, blue, yellow, respectively. For $i = 1, 2, 3$, define sets $S_i$ by \[S_i := \{(x_1, x_2, x_3) \in M^3 \mid x_1 + x_2 + x_3 \equiv 0 \pmod{n}, \quad x_{i + 1}, x_{i + 2} \; \text{are the same color}\},\] where the indices for $x_{i + 1}, x_{i + 2}$ are taken modulo $3.$ Observe that there are precisely $n^2$ triples $(x_1, x_2, x_3) \in M^3$ that satisfy $x_1 + x_2 + x_3 \equiv 0 \pmod{n}$, because if we fix $x_1, x_2$, there is a unique solution for $x_3$ in $\mathbb{Z}/n\mathbb{Z}.$ Furthermore, note that every triple $(x_1, x_2, x_3)$ for which $x_1 + x_2 + x_3 \equiv 0 \pmod{n}$ belongs to either $B$ or $S_1 \cup S_2 \cup S_3.$ Finally, remark that $|S_1| = |S_2| = |S_3|$ by symmetry, and $|S_1 \cap S_2| = |S_2 \cap S_3| = |S_3 \cap S_1| = |S_1 \cap S_2 \cap S_3| = |A|$, because any triple belonging to at least two of the $S_i$'s must have all three elements the same color. Therefore, by Inclusion-Exclusion we obtain \[n^2 = |B| + |S_1 \cup S_2 \cup S_3| = |B| + 3|S_1| - 2|A|.\] Therefore, it is sufficient to show that $3|S_1| \ge n^2.$ As earlier, if we fix $x_2, x_3 \in M$ of the same color, there is a unique $x_1$ in $M$ for which $x_1 + x_2 + x_3 \equiv 0 \pmod{n}.$ Hence, $|S_1| = r^2 + b^2 + y^2 \ge \tfrac{1}{3}(r + b + y)^2 = \tfrac{1}{3}n^2.$ $\square$
28.05.2022 09:40
Let $R(x)=\sum\limits_{t \text{ red}} x^t$ and define $B, Y$ for blue, yellow resp. Let $\omega$ be a primitive $n$th root of unity. Note $2|A|-|B|=\frac 2n \sum\limits_{j=0}^{n-1} R(\omega^j)^3+B(\omega^j)^3+Y(\omega^j)^3 - 3R(\omega^j)B(\omega^j)Y(\omega^j)$ If $1\le j\le n-1$, observe $R(\omega^j)+B(\omega^j)+Y(\omega^j)=\frac{\omega^{jn}-1}{\omega^j-1}=0$. Since this is a factor of $R^3+B^3+Y^3-3RBY$ it vanishes. Therefore we need to prove $R(1)^3+B(1)^3+Y(1)^3\ge 3R(1)B(1)Y(1)$ which is clear by AM-GM.
28.05.2022 11:05
For a color $c\in\{\text{red},\text{yellow},\text{blue}\}$, let $M_c\subset M$ be the subset of elements with color $c$. Moreover let $r=|M_\text{red}|$, $y=|M_\text{yellow}|$ and $b=|M_\text{blue}|$. Define $$S\doteqdot\{(x_1,x_2,x_3)\in M^3\mid x_1+x_2+x_3\equiv 0\pmod n\}.$$Observe that $|S|=n^2$, because if we fix $x_1,x_2$, there is a unique solution for $x_3$ in $\mathbb{Z}/n\mathbb{Z}$. Let $X$ be the set of ordered triples $(t,i,c)$ where $t$ is a tuple in $S$, $i\in\{1,2,3\}$ is an index and $c\in\{\text{red},\text{yellow},\text{blue}\}$ is a color such that $x_{i+1},x_{i+2}\in M_c$, where indices are modulo $3$. We count $|X|$ in two ways. First, we fix $i,c$. There are $|M_c|$ possibilities for each of $x_{i+1}$ and $x_{i+2}$. This gives $|M_c|^2$ elements of $X$ for each fixed pair $(i,c)$. Therefore $$|X|=\sum_{i=1}^3\sum_{\text{color }c}|M_c|^2=3(r^2+y^2+b^2).$$Second, we fix a tuple $t$. If $t\in A$ then there are exactly $3$ possibilities for $(i,c)$. If $t\in B$ then there are no possibilities for $(i,c)$. Otherwise, there is exactly one possibility for $(i,c)$. Therefore $$|X|=3|A|+(|S|-|A|-|B|)=n^2+2|A|-|B|.$$We conclude that $$2|A|-|B|+n^2=3(r^2+y^2+b^2).$$Hence the inequality $2|A|\ge|B|$ is equivalent to $3(r^2+y^2+b^2)\ge n^2$. It is true since $r+y+b=n$ and $$3(r^2+y^2+b^2)\ge (r+y+b)^2=n^2.$$
31.05.2022 15:49
So beautiful...