There are points on the plane, no three of which are collinear. Each pair of points is joined by a red, yellow or green line. For any three points, the sides of the triangle they form consist of exactly two colours. Show that .
Solution
It suffices to show that the case is impossible since we can remove extra points. For the th point, let be the numbers of lines having this point as an endpoint which are in red, yellow, and green respectively.
For any , WLOG assume and are red. Then this triangle corresponds to two red lines from , and this correspondence is one-to-one. It follows that the number of triangles is
But then it is clear that there are triangles. By the pigeonhole principle, WLOG assume
This gives . Since , this implies .
We claim that one of is at least 6. Suppose on the contrary that . As , it suffices to check . In all cases, does not hold.
WLOG assume . Suppose are red. By assumption, none of the lines formed by is red. Since , there must be a yellow or green triangle among these 6 points, contradiction. This proves .