2
$\begingroup$

This question already has an answer here:

Suppose you draw $n \ge 0$ distinct lines in the plane, one after another, none of the lines parallel to any other and no three lines intersecting at a common point. The plane will, as a result, be divided into how many different regions $L_n$? Find an expression for $L_n$ in terms of $L_{n-1}$, solve it explicitly, and indicate what is $L_{10}$.

I have tried to come up with a solution but cannot. A little guidance would be very helpful.

$\endgroup$

marked as duplicate by Joel Reyes Noche, user147263, Rebecca J. Stones, Najib Idrissi, Peter Taylor Mar 12 '15 at 10:47

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 3
    $\begingroup$ Please give your questions more descriptive titles. People who are searching the site need to be able to see what a question is about from its title. $\endgroup$ – Zev Chonoles Sep 28 '13 at 18:51
  • 2
    $\begingroup$ I feel like a similar question has been asked before but don't know where I might find the question. Does anyone know if this is a duplicate? $\endgroup$ – Dan Rust Sep 28 '13 at 18:54
  • 1
    $\begingroup$ math.stackexchange.com/questions/339750/… $\endgroup$ – Magdiragdag Sep 28 '13 at 18:57
4
$\begingroup$

Each new line intersects other $n$ lines in one point and divides each previous region of space into two regions. Therefore each new line adds new $n+1$ region and so we have: $$ L_{n+1}=L_n+n+1 $$ with $L_1=2$.

Indeed you can see that $L_n=1+\frac{n(n+1)}{2}$ and hence $L_{10}=56$.

$\endgroup$
4
$\begingroup$

HINT: If you already have $n$ lines and add an $(n+1)$-st line, the new line crosses each of the original $n$ lines. Those intersections divide the new line into $k+1$ segments (including the two unbounded segments). Show that each of those segments divides one old region into two new ones. This gives you a recurrence expressing $L_{n+1}$ in terms of $L_n$, and it’s an easy recurrence to solve for a closed form.

$\endgroup$
  • $\begingroup$ To show that each of those segments divides one old region into two new ones- would proof by induction be sufficient? If not what other ways can be used? $\endgroup$ – jimo Feb 22 '16 at 17:41
  • 1
    $\begingroup$ @diplodocus: It’s simpler than that: you merely have to observe that if you draw a straight line through a bounded region, you divide the region into two regions, one on each side of the line, and that the same thing happens when you draw a straight line through an unbounded region. A rigorous proof of this fact requires some pretty heavy-duty topology, but in an elementary course in combinatorics you can take it as pretty much self-evident. $\endgroup$ – Brian M. Scott Feb 22 '16 at 19:57

Not the answer you're looking for? Browse other questions tagged or ask your own question.