0
$\begingroup$

I don't know what this has to do with combinatorics, but it appeared in an exam last year.

In a plane, $n$ lines should be drawn, so that the amount of resulting areas are maximal. The amount of resulting areas is denoted as $L_n$

How can one show, that the following is possible?

A line can be drawn in the plane, so that it intersects all the previously existing lines. At the same time it should not intersect with previously existing intersections. (Meaning that all intersections of the line with already existing lines should be different)

So I thought that it could look like below and then the next line, f.ex. $h$ would intersect $g$ and the next line, f.ex. $i$ should intersect both $h$ and $g$ without intersecting any previous existing intersections.

But I don't know how to write this formally and how to find a recursion formula for $L_n$. enter image description here

$\endgroup$
1
  • $\begingroup$ Proof by induction. Show that it is true in some base case. If it is true for some number $n$, show that one additional line can always be added to the plane. $\endgroup$
    – Doug M
    Commented Nov 29, 2018 at 20:42

1 Answer 1

1
$\begingroup$

"Is the following possible?" - Yes. Just note that if you already have $n$ distinct lines in the plane, then you can surely pick a line $\ell$ that is not parallel to any of these (because there are infinitely many directions to choose from and only finitely many to avoid). Among the infinitely many parallels to $\ell$, there is certainly one that avoids the finitely many intersection points between the previous $n $lines. Take ons such line as line $n+1$.

With the above construction, the new line number $n+1$ will have $n$ distinct intersection points on it, thereby being split into $n+1$ segments (with two of the segments infinite). Each of these segments cuts a region in two. Therefore we have the recursion $$L_{n+1}=L_n+n+1 $$

$\endgroup$
1
  • $\begingroup$ Thank you very much, that helped a lot. Do you also know how one can get a closed form for $L_n$ with the help of $L_{n+1} = L_n + n + 1$? $\endgroup$
    – Math Dummy
    Commented Nov 29, 2018 at 20:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .