Dividing a circle into areas (Moser's Circle Problem)

Problem: If we put two points on a circle and connect them, we get two regions. Three points give 4 regions. If we continue this process, connecting every point to every other point and making sure no three lines meet at one point, we get:

(*diagram up to the problematic n=6 to the right)

Points (n) Number of regions (r)
1 1
2 2
3 4
4 8
5 16

We could now conjecture that \(r=2^{n-1}\). However, if we carefully draw the case for \(n=6\), we see that \(r=31\), not \(32\) as we would expect. Therefore, prove an nth term formula for this sequence.

Solution:

We can solve this problem by induction (although other methods exist). Let's experiment with a small case first. Consider \(n=4\) and add a point to get to \(n=5\) like so:

We see that the number of new regions that are added is determined by how many intersections the new lines make with the old lines.

Let us number the points on our circle in order (sticking with \(n=5\) only for ease of explanation), such that the point we have just added is numbered \(n\):

Notice that to find the number of intersections that each new line has with old lines, we can consider the number of points to the left of the line and the right of the line, since any old line going from left to right will cross our new line. For a point numbered \(i\), there are \(n-i-1\) points to the left, and \(i-1\) points to the right, and so \((n-i-1)(i-1)\) lines that cross our new line.

Now notice that \(x\) intersections will create \(x+1\) new regions. For example, the line from 5 to 2 has 2 intersections and creates 3 new regions:

Now let \(f(n)\) be our nth term formula for the number of regions created by n points on a circle. We know that by adding a point, each new line to a point \(i\) creates \((n-i-1)(i-1)+1\) new regions. So we can sum this across all points \(i\) to give the total number of new regions:

\[\sum_{i=1}^{n-1} (1+(n-i-1)(i-1))\]

Therefore:

\[f(n)=f(n-1)+\sum_{i=1}^{n-1} (1+(n-i-1)(i-1))\]

\[f(n)=f(n-1)+\sum_{i=1}^{n-1} (2-n+ni-i^2)\]

\[f(n)=f(n-1)+\sum_{i=1}^{n-1} 2 - \sum_{i=1}^{n-1} n + \sum_{i=1}^{n-1} ni - \sum_{i=1}^{n-1} i^2\]

\[f(n)=f(n-1)+2\sum_{i=1}^{n-1} 1 - n \sum_{i=1}^{n-1} 1 + n \sum_{i=1}^{n-1} i - \sum_{i=1}^{n-1} i^2\]

\[f(n)=f(n-1)+2(n-1) - n(n-1) + n \left(\frac{1}{2} (n-1) n \right) - \left(\frac{1}{6}(n-1)(n)(2n-1)\right)\]

\[f(n)=f(n-1)+\frac{1}{6} n^3 -n^2+\frac{17}{6} n -2\]

Now we can see that each time we add a point, we increase the number of areas by this cubic in \(n\), starting with one region for \(n=0\). Therefore:

\[f(n)=\sum_{r=1}^{n} \left( \frac{1}{6} r^3 -r^2+\frac{17}{6} r -2 \right)+1\]

We can evaluate this like before by using the formulas for the sums of \(k^3\), \(k^2\) and \(k\), giving:

\[f(n)=\frac{n}{24}(n^3-6n^2+23n-18)+1\]

\[f(n)=\frac{1}{24}(n^4-6n^3+23n^2-18n+24)\]

And this is our nth term formula.

 

(0 Votes)