There are 2n+3 points in the plane, no three of them collinear and no four of them concyclic.

Malahal assures me this is a Chinese Mathematical Olympiad question
from 1987.  I guess I've played with so many Voronoi diagrams that this
seems like a geometry exercise, but perhaps it is difficult.

karr@cs.cornell.edu (David Karr) provides an inversion-based proof, but
that's a little more complicated than necessary.  Try this.

Choose two points X,Y arbitrarily from the set S, and consider the set
of all circles passing through X and Y.  The centers of those circles
will lie on the line L that is the perpendicular bisector of XY.  For a
point P on L, let C(P) be the circle with center P through X and Y.
For each of the 2n+1 points Zi in S\{X,Y}, there will be a point Pi on
L for which C(Pi) passes through X, Y, and Zi.  The stated assumption
of general position implies that these points exist and are different.
The 2n+1 points Pi divide the line L into 2n+2 pieces: 2n finite
segments and 2 infinite rays.

Let f(P) be the number of points of S interior to C(P) minus the number
of points of S exterior to C(P).  If P is in one of the 2n+2 pieces of
L\{Pi}, then there are 2n+1 points of S not on C(P), so f(P) will be
odd.  Furthermore, f(P) will be constant along each piece.  As P moves
from a piece to an endpoint, a point of S on the exterior or interior
of C(P) will arrive on C(P), so f(P) will increase or decrease by 1.
Continuing to the next piece, the point will move to the interior or
exterior, for another unit increase or decrease in f(P).  For P on one
of the 2 infinite ray parts of L, C(P) can be taken arbitrarily close
to the line XY, and so partitions the set S in the same way as XY does.
The difference between the rays is that the sense of interior versus
exterior is opposite for C(P) on one ray versus the other.  Therefore
f(P) on one ray is the negative of f(P) on the other ray.

Taking f(P) for each piece and point in order along L, we traverse a
sequence of integers from a number to its negative.  So there must be a
point at which f(P)=0, and C(P) is the circle Q.E.D.

> 2. Try proving the stronger result that there are at least
>    (2n+3)(n+1)/3 such circles.

There are C(2n+3,2) = (2n+3)(n+1) ways of choosing X,Y above; each
yields at least one circle.  Each circle arises from three pairs of
points, so there are at least (2n+3)(n+1)/3 circles.

> 3. Is that bound achievable?

This I don't know, even if we allow Ceiling((2n+3)(n+1)/3) circles.  I
also do not know of a good upper bound for the number of such circles.

-- Dan Hoey <Hoey@AIC.NRL.Navy.Mil>

Pick any pair of points, A and B, and let L be the line between them.
The center O of any circle C through A and B will lie on the
perpendicular bisector M of AB.  Say M runs from left to right.  If O
is very far to the right of A and B, C will contain all points to the
right of L---k of them, say.  If O is very far to the left, C will
contain all points to the left of L; there will be 2n+1-k of these.
Without loss of generality, let k <= n.  Then as we move O from the
right to the left, the number of points in C changes from k to 2n+1-k
by steps of +1 and -1, so at some time it must change from n to n+1; at
this time C is one of our desired circles.  To complete the proof, note
that we can perform this construction once for each pair of points, or
C(2n+3,2) times, and that we get any given circle, going through A, B,
and D, say, at most three times---once from (A,B), once from (A,D), and
once from (B,D).  Hence we end up with at least C(2n+3,2)/3 =
(2n+3)(n+1)/3 circles.

ObPuzz: Given 2n+5 points, no 3 collinear and no 6 co-conic, show that
there are at least C(2n+5,4)/5 conics splitting the set of points into
n on one side of the conic and n on the other.  (If you're confused
about which side of a hyperbola is which, look on the projective
plane.)

-- David Moews <dmoews@xraysgi.ims.uconn.edu>