Please be as detailed as possible! Suppose you have drawn n lines in the plane i

Question

Please be as detailed as possible!

Suppose you have drawn n lines in the plane in general position (i.e. no two lines are parallel and no three lines intersect at a point). Into how many regions do the lines divide the plane? Hint: Use Euler's formula. Though there are many infinite regions, you can make them all finite by drawing a large circle around the picture which encloses all the intersection points of the lines, and only considering the picture inside the circle. Note: If you choose to submit a solution that doesn't use Euler's formula, you must fully justify every step; you cannot just notice patterns in examples

Explanation / Answer

Let f(n) denote the number of regions for n lines no three of which coincide in one point. This latter condition will guarantee the maximum. Obviously, f(0)=1, f(1)=2, f(2)=4, f(3)=7, etc.

Now, given n-1 lines, there are already f(n-1) regions. With the introduction of the n-th line, imagine the points of intersection of the pre-existing n-1 lines fall on one side of the n-th line. So, on one side of the n-th line -- where the points of intersection lie -- you still have f(n-1) regions, whereas on the other side of the n-th line, you now have n regions. So, for these n lines before us, the total number f(n) of regions must be equal to f(n-1)+n.

So, f(n)=f(n-1)+n.

With the initial condition(s) given earlier, this gives us f(n)=1+n(n+1)/2.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---