MathLabs

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 1 of 5: Define the separation parity
Previous stepNext step
n(x,y)=#{ℓ∈L:ℓ separates x and y}(mod2)n(x,y)=\#\{\ell\in L:\ell\text{ separates }x\text{ and }y\}\pmod 2
Detailed analysis

For two points x and y, let n(x,y) be the number of lines of L separating them, considered modulo 2. Choose a point p in S and color p blue; color q blue when n(p,q) is odd, and red when it is even.