Complex Combinatorics Hexagon/Triangle Contest Problem The problem is as follows:
The six sides of convex hexagon $A_1A_2A_3A_4 A_5A_6  $ are colored red. Each of the diagonals of the hexagon is colored either red or blue. Compute the number of colorings such that every triangle $A_iA_jA_k$ has at least one red side.
I just wasn't sure how to start this. I tried finding out if there was a minimum number of red diagonals for this to be true, but I couldn't find a consistent answer.
 A: Note that there are only two triangles which don't have a side which is an edge of the hexagon: $A_1A_3A_5$ and $A_2A_4A_6$. Hence, if a coloring is such that every triangle does not have at least one red edge, then at least $1$ of $A_1A_3A_5$ and $A_2A_4A_6$ has all blue edges (as all other triangles border a side).
We can now reduce the problem to finding the total number of colorings, and the number of colorings in which at least one of these triangles has all blue edges. 
Let's do the easy one first: There are $9$ edges which don't have a predetermined color, so we have $2^9$ total possible colorings.
We will use inclusion-exclusion to count the total number of colorings with at least $1$ blue triangle: $|A\cup B|=|A|+|B|-|A\cap B|$ where $A$ is the set of colorings with blue triangle $A_1A_3A_5$ and $B$ is the set of colorings with blue triangle $A_2A_4A_6$. 
$|A|=|B|=2^6$ since in each case there are $6$ edges with unspecified color.
$|A\cap B|=2^3$ since in this case there are $3$ edges with unspecified color.
Hence $|A\cup B|=2(2^6)-2^3=120$
Subtracting this from the total number of colorings gives us a final answer of $2^9-120=512-120=392$ colorings in which each triangle has at least $1$ red edge.
