×

# BdMO combinatorics question

What is the minimum number of lines needed to separate $$20$$ points on a plane?No 3 points lie on a straight line.

I have been struggling over this question for some time.It seems that the minimum number of lines corresponds with the maximum number of separations of a plane using some lines.Using 1 line,we divide plane into 2 regions.Using 2,we can make 4 separations.Using 3,we can make 7.There is a pattern here.Using this we can,with some easy calculation,figure out that it takes 6 lines to separate 22 points and 5 lines to separate 16.Therefore,the answer is 6.

The above holds true because using the (n+1)th line ,we can intersect n lines.We can obtain the recurrence $$a_n=a_{n-1}+n$$ with $$n>0$$ and $$a_0=1$$.Now I have the following questions:

1)Am I correct?

2)How can I,without solving the recurrence,figure out the formula for my sequence? I believe the last question can be resolved by any google search.So I am more interested in my first question and wondering if there is a better way to solve this.

Note by Rahul Saha
3 years, 8 months ago

Sort by:

The 20 points are fixed or you can move the points as you want?

- 3 years, 8 months ago

As the question doesn't put any restrictions,I think the points aren't fixed.

- 3 years, 8 months ago