# Cut circle with straight lines

Problem: To cut a circle with $n$ straight lines into the greatest number of possible parts.

What is the greatest number and how can you prove it is optimal?

• e.g. $7$ for $n=3$? Nov 23 '13 at 20:20
• A hint: Forget about the circle. Just cut the plane in as many parts as possible, then draw a circle containing all points of intersection, and finally shrink the figure to the desired size. Nov 23 '13 at 20:49
• Yea just worked this out with the same answer, but how do you show that you can carry on indefinitely intersecting the existing n-1 lines with the nth line ? Nov 23 '13 at 21:40

the number of parts is $\binom{n}{2}+\binom{n}{1}+\binom{n}{0}$

I'll give you a hint first, consider what happens when you add a new line to the circle. How many lines intersect it? and how many new parts does that create?

Note that this problem generalizes to $n$ planes cutting a sphere: for that, the number of parts would be $\binom{n}{3}+\binom{n}{2}+\binom{n}{1}+\binom{n}{0}$. Use recursion to prove and by using the formula for the original problem.

Make the $n$th line cross $n-1$ lines to get the maximal number of partitions. The first division gives $2$ of course, the second line $4$, and the $3$rd line $7$. For the $4$th line you get $11$ sections by this algorithm:

$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$

For each $n$, you add $n-1$ sections, so the total number of sections is: $$2 + 2 + 3 + 4 + \ldots = \frac{n^2 + n + 2}{2}$$ This sequence is A000124.

• How did you draw the image out of interest? Also, is it possible to prove that the number of new partitions is always $n$ if $n>1$ or is this just "obvious"? Nov 24 '13 at 9:46
• @marshall - it's "obvious" since if you cross each previous line ($n-1$ of these$) each partition now becomes$2$partions, meaning you have added$n-1$. Nov 24 '13 at 18:59 • But you add$n$partitions not$n-1\$. For example, the second line adds two partitions. Nov 24 '13 at 19:37