$\textbf{Question:}$
(APMO 1999.) Let
S
be a set of $2n+1$ points in the plane such that no three are
collinear and no four concyclic. A circle will be called
good
if it has 3 points of
S
on
its circumference,
n
−
1 points in its interior and
n
−
1 points in its exterior. Prove
that the number of good circles has the same parity as
n
.
$\textbf{My progress so far:}$
I have been able to show that for any two points (say A,B) among those there exist at least one good circle that goes through them.
Take a line through those two points(say l).Then one side of that line contains at least $n-1$ points.
Then there is a circle (for which the larger arc AB is on the "more point" side) large enough to contain all the points from that side.Now,we can use some "sweeping argument" like we continiously transform the circle to one that contains none of the point from that side.But the no 4 concyclic condition then gives us that the number of points in that circle cant be decreased more than one at any point.My claim follows from here.
I had no luck with this problem after this.
Best Answer
I'd like to try answering the question. The statement we need is that for any pair of points we can find an odd number of good circles (Lemma 1). We know that the number of pairs of points we can choose is $$ \frac{(2n+1)2n}{2} = n(2n+1) $$ and has the parity of $n$. Obviously, the sum of $n(2n+1)$ odd numbers will have the parity of $n$.
Sketch of proof of Lemma 1. Consider your "swiping argument". Let there be $m$ points on the left and $k$ points on the right. Consider the "swiping" function -- number of points inside the circle. Points are crossing the circle one by one (no $4$ points on the circle). This function has a plot that starts at $m$ and ends at $k$. How many times does this plot cross horizontal line $n-1$? At least once (since $m+k = 2n-1$ it is obvious that one one of them is greater than $n-1$ and one of them is smaller). It can cross the line more times ($3$, $5$, etc.), but that should be always an odd number, otherwise it cannot start below (above) $n-1$ and end above (below) $n-1$.
UPDATE It seems there are certain details I have overlooked (thanks to @Calvin Lin for pointing the issue). I will insert here a link to the solution and take some time to reconsider Lemma 1.