Let S be a set of n lines in a plane such thatno two are parallel and no three m

Question

Let S be a set of n lines in a plane such thatno
two are parallel and no three meet in the same point.
Show, by induction, that the lines in S determineO(n2)
intersection points.

Explanation / Answer

Let S be a set of n lines in a plane such that notwo are parallel and no three meet in the same point. Show, byinduction, that the lines in S determineO(n2) intersection points. n = 2 -> 2 non-parallel lines must intersect in one point.O(n2) points. Let us assume for n = k, k lines in set S determineO(k2) intersection points. We will prove for n = k+1, Now existing k lines intersect in O(k2)points. A new line k +1, will intersect these k lines at exactly k pointssince no 3 meet in the same point and this new line is not parallelto any. Thus the total number of intersecting points isO(k2) + k+1 which is of the orderO((k+1)2) [(k+1)2= k2 + 2k + 1]. Hence proved.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.