Monochromatic Solution for $a+b=c$ Let the numbers $1,...,8$ be given. I have to construct a formula $\varphi$ (in CNF form) which is true iff there exists a coloring with 2 colors for those numbers, such that $a+b=c$ has a monochromatic solution for $1 \le a \le b \le c \le 8$. 
What does it mean the equation has a monochromatic solution? In this excercise, does it mean that $a \ne b \ne c$? Because if $a=b$, that means both $a$ and $b$ has the same color and I have to select another color for $c$. 
For $a=4$ there exists only one monochromatic solution $b=4 \land c=8$. 
But I have no idea how to construct such a formula.
 A: A monochromatic solution is a triple $(a,b,c)$ with $a+b=c$ in which $a$, $b$, and $c$ are all assigned the same color. For example, if we color the integers $$\color{red}{1}, \quad \color{red}{2}, \quad \color{blue}{3}, \quad \color{blue}{4}, \quad \color{red}{5}, \quad \color{red}{6}, \quad \color{blue}{7}, \quad \color{blue}{8}$$
then $\color{red}{1} + \color{red}{1} = \color{red}{2}$ and $\color{blue}{3} + \color{blue}{4} = \color{blue}{7}$ are monochromatic solutions, but $\color{blue}{3} + \color{red}{5} = \color{blue}{8}$ and $\color{red}{2} + \color{red}{2} = \color{blue}{4}$ are not.
Your goal is probably to write down a CNF which is true iff a coloring exists with no monochromatic $a+b=c$. (It's obvious that one exists with some monochromatic $a+b=c$, since we can just color everything the same color.) In that case, there are two approaches:


*

*For each $i$ between $1$ and $8$, define variables $r_i$ and $b_i$ to be true if $i$ is red and if it's blue, respectively. Add clauses such as $(r_1 \lor b_1) \land (\neg r_1 \lor \neg b_1)$ to make sure that each number gets exactly one color, and clauses such as $(\neg r_3 \lor \neg r_4 \lor \neg r_7) \land (\neg b_3 \lor \neg b_4 \lor \neg b_7)$ to make sure each $a+b=c$ is not monochromatic.

*For each $i$ between $1$ and $8$, define a variable $x_i$ to be true if $i$ is red and false if $i$ is blue. Then you can do the same thing, but you only need $8$ variables.


(Obviously, approach 2 is more concise, but approach 1 generalizes easily to any number of colors.)
