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

  • 0
    http://www.arbelos.co.uk/Papers/Chords-regions.pdf2017-01-06

3 Answers 3

0

Answer is located here:

  • 0
    This link is just a repetition of the question.2016-10-06
6

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

1

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