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.

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

## Comments

Sort by:

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

Log in to reply

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

Log in to reply