# Maximum number of regions formed by points on a circle

The question is :

6 points are located on a circle and lines are drawn connecting these points, each pair of points connected by a single line. What can be the maximum number of regions into which the circle is divided?

My answer is 32 . But the actual answer is 31 how ??

• This link is just a repetition of the question. – Alex Oct 6 '16 at 11:06

In general the maximum number of regions you can get from $n$ points is given by

$${n \choose 4} + {n \choose 2} + 1$$

This can be proved using induction (other combinatorial proofs exist too). For more information (including at least two proofs), see this: Dividing a circle into areas.

This is an oft cited puzzle to show the perils of generalizing based on first few values. We get powers of $2$ till $n=5$, after which we get $31$.

The more general case is stated far more elegantly here: Number or regions formed when $$n$$ points on a circle are joined. But sometimes having a concrete example helps, and I hope this does.

Note that a new region is formed

1. when a new chord is drawn
2. whenever that new chord intersects another chord

We'll assume there are no 3-way intersections for the moment. However, it seems like 2 points divide the circle into 2 areas, 3 into 4, 4 into 8, 5 into 16, and so the pattern keeps working. Here is what happens for $$n=6$$: Let's draw a circle with points $$a_1$$, $$a_2$$, $$a_3$$, $$a_4$$ and $$a_5$$. Now put $$a_6$$, without loss of generality, between $$a_1$$ and $$a_5$$.

• $$a_1a_6$$ and $$a_5a_6$$ each add one section to the circle, no more. That's 2.
• we'll also ignore any intersections with other segments inside the circle for the moment and note $$a_2a_6$$/$$a_3a_6$$/$$a_4a_6$$ also create at least one more section. That's 3.
• $$a_3a_6$$ runs across a few lines, but which? $$a_1$$ and $$a_2$$ are on one side of it, but $$a_4$$ and $$a_5$$ are on the other. Therefore ($$a_1$$ or $$a_2$$) to ($$a_4$$ or $$a_5$$) may cross $$a_3a_6$$ inside the circle, but no others. That's 4.
• $$a_2a_6$$ runs across a few lines too: $$a_1$$ and $$a_3$$/$$a_4$$/$$a_5$$ are on each side. Therefore $$a_1a_3$$, $$a_1a_4$$, and $$a_1a_5$$ all may intersect with $$a_2a_6$$ to create another region. That's 3.
• $$a_4a_6$$ is similar to $$a_2a_6$$. $$a_4a_6$$ will intersect $$a_1a_5$$, $$a_2a_5$$, and $$a_3a_5$$. That's 3.

Thus the maximum number of additional regions moving from $$n=5$$ points to $$n=6$$ points is 2+3+4+3+3, or 15.

I included a diagram below to show what lines are added with a 6th point. I hope it helps you see things.