Circle-separable colorings of finite set of points in the plane

Question

This is problem 12093 of the American Math Monthly, published a few months back:

Let $S$ be a finite set of points in the plane no three of which are collinear and no four of which are concyclic. A coloring of the points of S with colors red and blue is circle- separable if there is a circle whose interior contains all the red points of $S$ and whose exterior contains all the blue points of $S$. Determine the number of circle separable colorings of $S$.

It seems the number of colorings is, remarkably, independent of the configuration of the points. Let $n=|S|$. In addition to the trivial colorings where red circles contain only one point or none at all (in total $(n+1)$ of them), it seems that every pair of points uniquely determine a circle-separable coloring, and every three out of these $n$ also determine uniquely a circle-separable coloring.

Answer 1

Let the number of circle seperable colourings for $n$ points be $f_n$. By rearranging, we see that to show $f_n$ is as described, we just need to show $f_{n}-f_{n-1}={{n}\choose 2}+1$

For this, fix a point $P$, and note that we have a bijection between $n-1$ circle seperable colourings without $P$, and $n$ circle seperable colourings where $P$ has no choice in its colour. Thus, we may identify $f_{n+1}-f_n$ with the number of CSCs where $P$ has a choice in its colour. The space of circles/lines which seperate two sets of points in the plane is connected, so we have that if $P$ has a choice in its colour given a CSC on the rest, it can be taken to lie on the seperating circle (intermediate value theorem), and perturbing the circle yields the two choices of colour.

Given a partition of the points without $P$ admitting a seperating circle passing through $P$, then sometimes we can colour the partition red/blue in both ways, if our circle's interior can be taken to contain either part of our partition. This is determined by the side on which $\infty$ is on, viewing this as taking place on $\mathbb{CP}^1\cong S^2$. So apply a mobius transformation $\mu$ taking $P$ to $\infty$, now we have $n-1$ points in the plane, and a new point $\mu(\infty)$, and CSCs admitting a circle passing through $P$ are just lines seperating this set. This set has no three points collinear by our hypothesis, and thus it suffices to show that the number of seperating lines in ${n\choose 2}+1$. But this is a simple induction, adding an extra point $Q$ going from $n-1$ to $n$ adds $n$ new seperating lines, corresponding to the $n$ potential seperating lines that pass through $Q$.

There is also probably a cleverer non inductive proof for this last point, but I think the main trick is to mobius transform a point to $\infty$.

Answer 2

Below, whenever we are considering a circle determined by two points or three points, we mean that the radius of the circle is just large enough to cover the two or three points respectively.

For $n=1$, there are clearly two trivial colorings; for $n=2$, there are clearly four colorings. For $n\geq 3$, we show there are ${{n}\choose{0}}+{{n}\choose{1}}+ {{n}\choose{2}} + {{n}\choose {3}}$ colorings, where $n=|S|$ is the cardinality of $S$.

Clearly, for any point P belonging to the set $S$, we can get a circle with a small enough radius, centered at $P$, so that the interior of the circle contains only $P$. In this way we get ${{n}\choose{1}}$ circle-separable colorings. Also, there are ${{n}\choose{0}}$ colorings where no point is labelled red .

Now choose any two points $A,B$ out of the $n$ points, and consider the line joining these two points. Extend this line $ \overleftrightarrow{AB}$ in both directions. Since no four points are concyclic and no three points are collinear, we must have some $k_{AB}$ of the remaining $(n-2)$ points on one side of the line segment, the remaining $(n-2-k_{AB})$ ones on the other side, and exactly none on the line segment $\overleftrightarrow{AB}$. Since none of the points are concyclic, all the points on one side of $\overleftrightarrow{AB}$ must subtend distinct angles on the segment $\overline{AB}$. The points on the other side of the line should also subtend distinct angles on $\overline{AB}$.

It is not very difficult to see that each of the $(n-2)$ points on either side of $\overleftrightarrow{AB}$ determines exactly one circle (where a circle is determined by $A,B$ and this third point all on the circumference of this circle), while there is one more 'extraneous' circle that is always obtained which either contains only $A,B$ on it's boundary, or is one containing $A,B$ on the boundary and all the points on one side of $\overleftrightarrow{AB}$ in it's interior.

As we choose any two out of our $n$ points, clearly each of the circles determined by the three points as above are counted thrice. Thus, the total number of actual distinct colorings obtained this way is just the sum of the number of all triangles ${{n}\choose{3}}$.

For two circles each determined by only two points, they can encircle exactly the same number of points (and hence essentially they're the same circle for our purposes) if both these pairs of points are each pairwise consecutive on the convex hull of our entire point set. But it is not hard to see from the previous paragraph that if we take two consecutive points on the convex hull of our point set, the 'extraneous' circle defined by these two points contains only these two points, which is a contradiction. Thus, for each of the ${n}\choose{2}$ pairs of points, we get a unique 'extraneous' circle.

Hence the total number of colorings is ${{n}\choose{0}}+{{n}\choose{1}}+ {{n}\choose{2}} + {{n}\choose {3}}$.