Problem 3
Let S be a set of 2004 points in the plane, no three collinear, and let L be the set of all lines determined by pairs of points of S. A line separates two points when they lie on opposite sides of it and neither lies on the line. Prove that S can be colored with at most two colors so that two points have the same color exactly when an odd number of lines in L separates them.
Step 3 of 5: Discard lines missing the triangle vertices
Detailed analysis
Draw the triangle pqr and its seven regions. Any line of L that passes through none of p,q,r crosses the sides of the triangle an even number of times, so its contribution to the three separation counts is even. Only lines through one of the three vertices and a point in one of the seven regions matter.