Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|cite|improve this question
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 2

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

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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