16th APMO 2004 Problem 3 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).
Problem 1039
Official solution
Let us denote by d XY 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 d XY is odd. This will work provided that given any three points A, B, C, we have d AB + d BC + d CA is odd. (For then if Y and Z are the same color, d XY and d XZ have th same parity, so d YZ is odd, which is correct. Similarly, if Y and Z are opposite colors, then d YZ 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 d AB + d BC + d CA . So we are interested in lines which pass through A and the (interior of) BC, and similarly for B, C. Let n 1 , n 2 , ... , n 7 be the number of points (excluding A, B, C) in the various regions (as shown). The number of lines through A and BC is n 1 + n 2 + n 3 . So d AB + d BC + d CA = (n 1 + n 2 + n 3 ) + (n 1 + n 4 + n 5 ) + (n 1 + n 6 + n 7 ) = n 1 + n 2 + n 3 + n 4 + n 5 + n 6 + n 7 = (2004 - 3) = 1 mod 2. Thanks to Dinu Razvan 16th APMO 2004 © John Scholes [email protected] 30 Mar 2004 Last corrected/updated 30 Mar 04