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 5 of 5: Conclude the coloring property
Detailed analysis
The identity in the previous step gives n(p,q)+n(p,r)+n(q,r) odd. Therefore n(q,r) is odd exactly when n(p,q) and n(p,r) have the same parity, which is exactly when q and r have the same color. The coloring uses only blue and red.