Waste less time on Facebook — follow Brilliant.

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
2 years, 8 months ago

No vote yet
1 vote


Sort by:

Top Newest

The 20 points are fixed or you can move the points as you want? Jorge Tipe · 2 years, 8 months ago

Log in to reply

@Jorge Tipe As the question doesn't put any restrictions,I think the points aren't fixed. Rahul Saha · 2 years, 8 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...