5
$\begingroup$

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 ??

$\endgroup$
0
$\begingroup$

Answer is located here:

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

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$.

$\endgroup$
1
$\begingroup$

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.

Example of 6th point added to Moser circle problem

$\endgroup$

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.