9 votes 9 votes Suppose $n$ straight lines are drawn on a plane. When these lines are removed, the plane falls apart into several connected components called regions. $A$ region $R$ is said to be convex if it has the following property: whenever two points are in $R$, then the entire line segment joining them is in $R$. Suppose no two of the n lines are parallel. Which of the following is true? $O (n)$ regions are produced, and each region is convex. $O (n^{2})$ regions are produced but they need not all be convex. $O (n^{2})$ regions are produced, and each region is convex. $O (n \log n)$ regions are produced, but they need not all be convex. All regions are convex but there may be exponentially many of them. Quantitative Aptitude tifr2013 quantitative-aptitude geometry cartesian-coordinates + – makhdoom ghaya asked Nov 6, 2015 • edited Aug 17, 2020 by soujanyareddy13 makhdoom ghaya 1.4k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes Regions divided by $n$ lines = $1+1+2+3+4+..........+n-1 = 1 + n(n-1)/2 = O(n^2)$ Option $B$ can be easily discarded as convex segments are obvious. Hence Option $C$ is correct. Nitesh Tripathi answered Dec 11, 2015 • edited Jul 25, 2021 by soujanyareddy13 Nitesh Tripathi comment Share Follow See all 7 Comments See all 7 7 Comments reply Arjun commented Dec 11, 2015 reply Follow Share how non-convex region is forming? 0 votes 0 votes Himanshu1 commented Dec 11, 2015 reply Follow Share I think answer should be C.. 0 votes 0 votes Nitesh Tripathi commented Dec 12, 2015 reply Follow Share sorry, my sloppy mistake. all regions are convex. Option C is correct. (edited the answer) 0 votes 0 votes jaco commented Nov 22, 2018 reply Follow Share No-convex regions are possible, isn't it? Please correct me if i am wrong. 1 votes 1 votes Gyanu commented Nov 10, 2019 reply Follow Share @Nitesh Tripathi I think region divided by n lines should be ---. n ( n + 1 ) / 2 + 1 See this https://www.cut-the-knot.org/proofs/LinesDividePlane.shtml 2 votes 2 votes JAINchiNMay commented Apr 28, 2021 reply Follow Share how all the regions are convex,i think non convex regions are also possible 0 votes 0 votes Venky8 commented Jun 8, 2021 reply Follow Share @jaco Straight lines extend to infinity in both directions. Also given in the question, no two lines are parallel. Yet you have taken two parallel vertical lines. I have corrected the line colored in blue. You can see that all regions are convex. And the number of regions in the link given by @Gyanu is correct. We can verify it. As we have 5 lines and they are placed appropriately to get the maximum number of regions. Therefore, Maximum number of regions is: $L_{n} = \frac{n(n+1)}{2} + 1 = \frac{5(5+1)}{2} + 1 = 16$ And indeed we have 16 regions in the figure. The formula given in the question is wrong. Please edit it, @Arjun sir. Anyway, Option C) is correct as $L_{n} = O(n^{2})$. 1 votes 1 votes Please log in or register to add a comment.
2 votes 2 votes L[4] | L[3]+4 | L[2]+3 | L[1]+2 | L[0]+1 | 1 L[n] = L[n-1]+n => = L[n-2]+(n-1)+n => = L[n-3]+(n-2)+(n-1)+n => = L[n-4]+(n-3)+(n-2)+(n-1)+n ...................................... ...................................... ...................................... ...................................... => = L(n-n)+(n-(n-1))+..........+(n-4)+(n-3)+(n-2)+(n-1)+n => = L[0]+1+2+3+4+..........+n ; Observing carefully the previous line will help you to understand how this(current line) came. => = 1 + n*(n+1)/2 ; we know summation of 1 to n numbers is (n+1)/2\ => = 1 + S(n) ; where, S(n) = n*(n+1)/2 = 1+2+3+4+..........+n So, finding 1 + S(n) will let us know the total regions after drawn n lines in a plane. Main Link→ https://sobujerkhuje.wordpress.com/2018/02/09/how-many-regions-do-n-lines-divide-a-plane/ samir757 answered Jun 22, 2021 samir757 comment Share Follow See all 0 reply Please log in or register to add a comment.