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 4 of 5: Count the seven regions

Previous step Next step

(n_1+n_4+n_7)+(n_2+n_5+n_7)+(n_3+n_6+n_7)=\sum_{i=1}^7n_i=2004-3=2001\equiv1\pmod2

Detailed analysis

Let n_i be the number of points of S in region i, excluding p,q,r, with the standard seven-region labeling around triangle pqr. Lines through p that separate q and r correspond to regions 1,4,7; the analogous regions for q and r are 2,5,7 and 3,6,7. Their sum counts every point of S other than p,q,r once, hence equals 2001, which is odd.