2014 IMO SL #C9

Consider a prism with pentagons $A_1A_2A_3A_4A_5$ and $B_1B_2B_3B_4B_5$ as the top and bottom faces is given. Each side of the two pentagons and each of the 25 segments $A_iB_j$ is colored red or green. Every triangle whose vertices are vertices of the prism and whose sides have all been colored has two sides of a different color. Prove that all 10 sides of the top and bottom faces have the same color.

First, we show that all $A_i$ are the same color. For the sake of contradiction, assume otherwise. Then, there exists a vertex, say $A_1$, such that $A_1A_2$ and $A_1A_5$ are different colors. Assume that $A_1A_2$ is green and $A_1A_5$ is red. Now consider the five edges $A_1B_i$ for $i=1,2,3,4,5$. Note that at least three of these five must be the same color (since there are only two colors to pick from). Assume that they are $A_1B_i, A_1B_j,A_1B_k$ and that the common color between these three is green. Next, consider the three triangles $A_1A_2B_i, A_1A_2B_j, A_1A_2B_k$, and note that the edges $A_2B_i, A_2B_j, A_2B_k$ must be red. Finally, two of $B_i, B_j, B_k$ are adjacent, but if our three edges are red, then we have a red triangle with $A_2$, and if they are green, then we have a green triangle with $A_1$. This gives us a contradiction, as such triangles are not allowed. 

So, we know that all $A_i$ are the same color. Similarly, all $B_i$ have the same color. 

Now it only remains to prove that all the $A_i$ have the same color as all the $B_i$. For the sake of contradiction, assume otherwise. We saw before that 3 of the 5 edges $A_1B_i$ must be the same color. If this color is red, then 2 of the 3 $B_i$ give a red triangle with $A_1$. So, those three edges must be green. Similarly, 3 of the 5 edges $A_2B_i$ must be green. However, there must be a $B_i$ in both of these sets, and that $B_i$ forms a green triangle with $A_1, A_2$.