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.

  • $\begingroup$ 1. Do you have a question? 2. I have one: what do you mean by the last two clauses of the last sentence? $\endgroup$ – Peter Taylor Jul 4 at 14:21
  • $\begingroup$ 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. $\endgroup$ – Aritro Pathak Jul 4 at 14:29
  • 1
    $\begingroup$ What circle contains $(0, -100)$ and $(0, 100)$ but neither of $(-1, 0)$ or $(1, 0)$? $\endgroup$ – Peter Taylor Jul 4 at 15:03
  • 1
    $\begingroup$ 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. $\endgroup$ – Peter Taylor Jul 4 at 16:23
  • $\begingroup$ 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. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.