A set of 2n+1 points in the plane has no three collinear and no four concyclic. A circle is said to divide the set if it passes through 3 of the points and has exactly n - 1 points inside it. Show that the number of circles which divide the set is even iff n is even.
Solution
Take two of the points, A and B, and consider the 2n-1 circles through A and B. We will show that the number of these circles which divide the set is odd. The result then follows almost immediately, because the number of pairs A, B is (2n+1)2n/2 = N, say. The total number of circles which divide the set is a sum of N odd numbers divided by 3 (because each such circle will be counted three times). If n is even, then N is even, so a sum of N odd numbers is even. If n is odd, then N is odd, so a sum of N odd numbers is odd. Dividing by 3 does not change the parity.
Their centers all lie on the perpendicular bisector of AB. Label them C1, C2, ... , C2n-1, where the center of Ci lies to the left of Cj on the bisector iff i < j. We call the two half-planes created by AB the left-hand half-plane L and the right-hand half-plane R correspondingly. Let the third point of the set on Ci be Xi. Suppose i < j. Then Ci contains all points of Cj that lie in L and Cj contains all points of Ci that lie R. So Xi lies inside Cj iff Xi lies in R and Xj lies inside Ci iff Xj lies in L
Now plot f(i), the number of points in the set that lie inside Ci, as a function of i. If Xi and Xi+1 are on opposite sides of AB, then f(i+1) = f(i). If they are both in L, then f(i+1) = f(i) - 1, and if they are both in R, then f(i+1) = f(i) + 1. Suppose m of the Xi lie in L and 2n-1-m lie in R. Now suppose f(i) = n-2, f(i+1) = f(i+2) = ... = f(i+j) = n-1, f(i+j+1) = n. Then j must be odd. For Xi and Xi+1 must lie in R. Then the points must alternate, so Xi+2 lies in L, Xi+3 lies in R etc. But Xi+j and Xi+j+1 must lie in R. Hence j must be odd. On the other hand, if f(i+j+1) = n-2, then j must be even. So the parity of the number of C1, C2, ... , Ci which divide the set only changes when f crosses the line n-1 from one side to the other. We now want to say that f starts on one side of the line n-1 and ends on the other, so the final parity must be odd. Suppose there are m points in L and hence 2n-1-m in R. Without loss of generality we may take m <= n-1. The first circle C1 contains all the points in L except X1 if it is in L. So f(1) = m or m-1. Similarly the last circle C2n-1 contains all the points in R except X2n-1 if it is in R. So f(2n-1) = 2n-1-m or 2n-2-m. Hence if m < n-1, then f(1) = m or m-1, so f(1) < n-1. But 2n-1-m >= n+1, so f(2n-1) > n-1. So in this case we are done.
However, there are complications if m = n-1. We have to consider 4 cases. Case (1): m = n-1, X1 lies in R, X2n-1 lies in L. Hence f(1) = n-1, f(2n-1) = n > n-1. So f starts on the line n-1. If it first leaves it downwards, then for the previous point i, Xi is in L and hence there were an even number of points up to i on the line. So the parity is the same as if f(1) was below the line. f(2n-1) is above the line, so we get an odd number of points on the line. If f first leaves the line upwards, then for the previous point i, Xi is in R and hence there were an odd number of points up to i on the line. So again the parity is the same as if f(1) was below the line.
Case (2): m = n-1, X1 lies in R, X2n-1 lies in R. Hence f(1) = f(2n-1) = n-1. As in case (1) the parity is the same as if f(1) was below the line. If the last point j with f(j) not on the line has f(j) < n-1, then (since X2n-1 lies in R) there are an odd number of points above j, so the parity is the same as if f(2n-1) was above the line. Similarly if f(j) > n-1, then there are an even number of points above j, so again the parity is the same as if f(2n-1) was above the line.
Case (3): m = n-1, X1 lies in L, X2n-1 lies in L. Hence f(1) = n-2, f(2n-1) = n. So case has already been covered.
Case (4): m=n-1, X1 lies in L, Xn-1 lies in R. So f(1) = n-2, f(2n-1) = n-1. As in case (2), the parity is the same as if f(2n-1) was above the line.
(C) John Scholes
jscholes@kalva.demon.co.uk
11 Apr 2002