2004 points are in the plane, no three collinear. S is the set of lines through any two of the points. Show that the points can be colored with two colors so that any two of the points have the same color iff there are an odd number of lines in S which separate them (a line separates them if they are on opposite sides of it).
Solution
Let us denote by dXY the number of points separating the points X and Y. If the result is true, then the coloring is effectively determined: take a point X and color it blue. Then for every other point Y, color it blue iff dXY is odd. This will work provided that given any three points A, B, C, we have dAB + dBC + dCA is odd. (For then if Y and Z are the same color, dXY and dXZ have th same parity, so dYZ is odd, which is correct. Similarly, if Y and Z are opposite colors, then dYZ is even, which is correct.)
We are interested in lines which pass through an interior point of one or more of AB, BC, CA. Lines cannot pass through all three. If they pass through two, then they do not affect the parity of dAB + dBC + dCA. So we are interested in lines which pass through A and the (interior of) BC, and similarly for B, C. Let n1, n2, ... , n7 be the number of points (excluding A, B, C) in the various regions (as shown). The number of lines through A and BC is n1 + n2 + n3. So dAB + dBC + dCA = (n1 + n2 + n3) + (n1 + n4 + n5) + (n1 + n6 + n7) = n1 + n2 + n3 + n4 + n5 + n6 + n7 = (2004 - 3) = 1 mod 2.
Thanks to Dinu Razvan
© John Scholes
jscholes@kalva.demon.co.uk
30 Mar 2004
Last corrected/updated 30 Mar 04