Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If there are N points on a circle, and you draw a chord between each of them, how many regions is the circle subdivided into?

I'm not quite sure where to begin. I know that there are at least n section for n points on a chord because if you connect each point on the circle with its adjacent point then that forms n sections. Whatever goes on in the middle though seems really arbitrary. Is there any good way of approaching this problem?

Thanks

share|improve this question
add comment

2 Answers

up vote 10 down vote accepted

Let's assume that no three lines intersect at the same point.

Consider what happens each time you add a line between two points. If it crosses $k$ other lines, it splits $k+1$ regions into two, thereby adding $k+1$ regions. Therefore, when a line is added, it can be considered to be adding $1$ region for the line and $1$ region for each point of intersection:

$\hspace{4.5cm}$chords $$ \text{Regions Split by a Line}\atop\text{Each Region is Paired with a Line or Point of Intersection} $$ Thus, we just need to count $1$ for the original region inside the circle, and add the number of lines, $\binom{N}{2}$, and the number of intersections, $\binom{N}{4}$.

Thus, there are $\binom{N}{4}+\binom{N}{2}+\binom{N}{0}$ regions.

Counting Lines and their Intersections

Note that given $N$ points on the circle, each pair of points yields a line, thus the number of lines connecting the points is $\binom{N}{2}$. For each set of $4$ points, there is a unique intersection of two lines, an "X in a quadrilateral" arrangement. Thus, the number of interior line intersections is $\binom{N}{4}$.

Non-Sequitur:

This is often given as an example of what happens if you attempt to guess a sequence from the first few terms since this sequence starts with $$ 1,2,4,8,16,\dots $$ but the next term is $31$.

Why:

The reason for the initial similarity of $\binom{n}{4\vphantom{0}}{+}\binom{n}{2\vphantom{0}}{+}\binom{n}{0}$ to the geometric progression is that $$ \sum_{k=0}^\infty\binom{n}{k}=(1+1)^n=2^n\tag{1} $$ and $$ \sum_{k=0}^\infty(-1)^k\binom{n}{k}=(1-1)^n=0^n\tag{2} $$ For $n>0$, adding $(1)$ and $(2)$ and dividing by $2$ gives $$ \sum_{k=0}^\infty\binom{n}{2k}=2^{n-1}\tag{3} $$ $\binom{n}{4\vphantom{0}}{+}\binom{n}{2\vphantom{0}}{+}\binom{n}{0}$ is the first three terms of $(3)$. The first time a non-zero term is left out of $(3)$ is when $n=6$, and that is when $\binom{n}{4\vphantom{0}}{+}\binom{n}{2\vphantom{0}}{+}\binom{n}{0}=31$.

share|improve this answer
    
Could you say a bit more about where exactly the $\binom{n}{2}$ and the $\binom{n}{4}$ come from, please? –  Peter Phipps May 19 '12 at 23:25
    
@Peter: I've added a small section on that. Let me know if you would like more. –  robjohn May 20 '12 at 0:22
    
Thanks, @robjohn. –  Peter Phipps May 20 '12 at 19:56
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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