1

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?

marshall
  • 729
  • 7
  • 22
  • e.g. $7$ for $n=3$? – shade4159 Nov 23 '13 at 20:20
  • 4
    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. – Christian Blatter 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 ? – stevie Nov 23 '13 at 21:40

2 Answers2

5

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.

iYOA
  • 1,388
  • 8
  • 20
2

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$ enter image description here

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.

Nathaniel Bubis
  • 33,018
  • 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"? – marshall Nov 24 '13 at 09: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$. – Nathaniel Bubis Nov 24 '13 at 18:59
  • But you add $n$ partitions not $n-1$. For example, the second line adds two partitions. – marshall Nov 24 '13 at 19:37