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

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.

• 1. Do you have a question? 2. I have one: what do you mean by the last two clauses of the last sentence? – Peter Taylor Jul 4 at 14:21
• The question is stated above; while I have an answer to it, the question seems interesting enough to share, in order to possibly see different approaches. I edited the last sentence to hopefully make it more clear. – Aritro Pathak Jul 4 at 14:29
• What circle contains $(0, -100)$ and $(0, 100)$ but neither of $(-1, 0)$ or $(1, 0)$? – Peter Taylor Jul 4 at 15:03
• I'm having second thoughts about that example, actually. The circle which has those two points as a diameter contains both of the other points, and so isn't counted under any other heading. – Peter Taylor Jul 4 at 16:23
• As you allude to above; you do have ${{4} \choose {0}}+{{4}\choose {1}}+{{4}\choose{2}}+{{4}\choose{3}}$ colorings; and exactly one out of the ${{4}\choose{2}}$ colorings is one where al four points are colored red. – Aritro Pathak Jul 4 at 17:39

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$$.