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.

## Comments

Sort by:

TopNewestThe 20 points are fixed or you can move the points as you want? – Jorge Tipe · 3 years, 1 month ago

Log in to reply

– Rahul Saha · 3 years, 1 month ago

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