# Separating points on a plane

BdMO 2011

There are $25$ points on a plane, no three of which lie on a line. Find the minimum number of lines needed to separate them from one another.

Can we assume that the points lie on a circle.I think not.I at first thought that the answer is 13,but realized that it probably isn't the correct answer.The way I tried to do it was by letting the points lie on a circle.Then I calculated the first few values and found a pattern and came to the (probably) erroneous conclusion that the answer is $13$.A nudge in the correct direction will be appreciated.

-
Don't assume they lie on a circle, but try to see the cases for smaller amount of points ($2,3,4,5,6\dots$) – Berci Jan 30 '14 at 12:44
@Berci,it seems that the answer depends on the maximum number of divisions of plane using n lines. – rah4927 Jan 30 '14 at 12:47

## 2 Answers

Answer depends upon the position of the points. Nevertheless, the number of minimum lines required to separate all points is always less than $[\frac{n+1}{2}]$, where $[x]$ denotes greatest integer less than equal to $x$.

-

It is well known that $n\geq0$ lines $g_k$ $\>(1\leq k\leq n)$ divide the plane into at most $$p_n={1\over2}(n^2+n+2)$$ compartments. (For an induction proof, use that $g_{n+1}$ intersects the first $n$ lines in at most $n$ points, which means that at most $n+1$ compartments are divided in two.)

Given $N$ points in the plane the minimal number $n$ of lines needed to "compartimentize" these points is characterized by $$p_{n-1}<N\leq p_n\ .$$ This is equivalent with $$n^2-n+2<2N\leq n^2+n+2\ ,$$ and finally leads to $$n=\left\lceil\sqrt{2N-{7\over4}} -{1\over2}\right\rceil\ .$$ When $N=25$ we obtain $n=7$. This means that we cannot do with less than $7$ lines, whatever the position of the $25$ given points.

This was easy, but maybe you are out for another kind of minimum: What is the minimal number $n=n(N)$ of lines that is sufficient for every position of the $N$ given points.

-