1
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ e.g. $7$ for $n=3$? $\endgroup$
    – shade4159
    Nov 23 '13 at 20:20
  • 3
    $\begingroup$ 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. $\endgroup$ Nov 23 '13 at 20:49
  • $\begingroup$ 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 ? $\endgroup$
    – stevie
    Nov 23 '13 at 21:40
5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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"? $\endgroup$
    – marshall
    Nov 24 '13 at 9:46
  • $\begingroup$ @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$. $\endgroup$
    – nbubis
    Nov 24 '13 at 18:59
  • $\begingroup$ But you add $n$ partitions not $n-1$. For example, the second line adds two partitions. $\endgroup$
    – marshall
    Nov 24 '13 at 19:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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