Going Around in Circles

If we pick any two distinct points on a circle, and connect them with a chord, the chord will divide the interior of the circle into two distinct, nonintersecting regions. If we pick three distinct points on a circle and connect each pair of them with a chord, we can form four distinct, nonintersecting regions. What is the maximum number of nonintersecting regions that we can form by selecting four distinct points on a circle and connecting each pair of them with a chord? By selecting five distinct points? Six distinct points? And of course, then, n distinct points?
Source: NCTM Problem to Ponder 11/2011

SOLUTION

One point: 0 chord, 0 intersection, 1 region


Two points: 1 chord, 0 intersection, 2 regions


Three points: 3 chords, 0 intersection, 4 regions


Four points: 6 chords, 1 intersection, 8 regions


Five points: 10 chords, 5 intersections, 16 regions


Six points: 15 chords, 15 intersections, 31 regions


Seven points: 21 chords, 35 intersections, 57 regions

We tabulate the previous data in the following table


Looking at the table, we easily notice a pattern:
Regions=Chords+Intersections+1
But, is it true for all values of n?
When we add a new point, the number of chords, intersections, and regions increase. But by how much? We will now examine in depth the transition from a 5-point circle to a 6-point circle in order to gain insights into the increase of these numbers.
Let R denote the number of regions; C the number of chords; I the number of intersections. We start from a 5-point circle as shown in the figure below

C=10,\; I=5,\; R=16
Now, let’s add a sixth point and draw chord A.
Chord A does not intersect any old chord and splits an old region into two. The number of regions R increases by 1 from 16 to 17.


Chord B intersects 3 old chords and splits 4 old regions into 8. R increases by 4 from 17 to 21.


Chord C intersects 4 old chords and splits 5 old regions into 10. R increases by 5 from 21 to 26.


Chord D intersects 3 old chords and splits 4 old regions into 8. R increases by 4 from 26 to 30.


Chord E does not intersect any old chord and splits an old region into two. R increases by 1 from 30 to 31.

Summary
When we add a point, we add several new chords. A new chord may intersect no old chord or may intersect several old chords at several intersection points. When a new chord intersects an old chord it leaves an old region and enters another old region splitting each old region it passes through into two. Hence, it follows that the increase in R will be one more than the increase in I including the case where the new chord does not intersect any chord. In other words,
\Delta R=\Delta I+1

Proof by induction
Show that R=C+I+1 for all positive integers n=1,2,3,\cdots
n=1
1=0+0+1
The formula is true for n=1

Suppose it is true for n. We write
R_n=C_n+I_n+1
We want to show that it is true for n+1, that is
R_{n+1}=C_{n+1}+I_{n+1}+1
When we add a point, we add a number of new chords. If the new chord does not intersect any old chord,
\Delta I=0
\Delta C=1
\Delta R=\Delta I+1
=0+1
=1
R_{n+1}=R_n+\Delta R
=R_n+1
C_{n+1}+I_{n+1}+1=\left (C_n+\Delta C\right )+\left (I_n+\Delta I\right )+1
=\left (C_n+1\right )+\left (I_n+0\right )+1
=\left (C_n+I_n+1\right )+1
=R_n+1
Comparing the equations we conclude that
R_{n+1}=C_{n+1}+I_{n+1}+1

If the new chord intersects k old chords at k intersection points
\Delta I=k
\Delta C=1
\Delta R=\Delta I+1
=k+1
R_{n+1}=R_n+\Delta R
=R_n+k+1
C_{n+1}+I_{n+1}+1=\left (C_n+\Delta C\right )+\left (I_n+\Delta I\right )+1
=\left (C_n+1\right )+\left (I_n+k\right )+1
=\left (C_n+I_n+1\right )+k+1
=R_n+k+1
Comparing the equations we conclude that
R_{n+1}=C_{n+1}+I_{n+1}+1
DONE

Now that we have proved the formula R=C+I+1, it is time to express it in terms of n.
A chord connects two points. How many ways can we select two points from a collection of n points?
C=\binom {n}{2}
Two chords (connecting four points) intersect at one point. How many ways can we select four points from a collection of n points?
I=\binom{n}{4}
The formula expressed in terms of the number of points n is
R=\binom{n}{2}+\binom{n}{4}+1

Verification
R_1=\binom{1}{2}+\binom{1}{4}+1
=0+0+1
=1

R_2=\binom{2}{2}+\binom{2}{4}+1
=1+0+1
=2

R_3=\binom{3}{2}+\binom{3}{4}+1
=3+0+1
=4

R_4=\binom{4}{2}+\binom{4}{4}+1
=6+1+1
=8

R_5=\binom{5}{2}+\binom{5}{4}+1
=10+5+1
=16

R_6=\binom{6}{2}+\binom{6}{4}+1
=15+15+1
=31

R_7=\binom{7}{2}+\binom{7}{4}+1
=21+35+1
=57

R_8=\binom{8}{2}+\binom{8}{4}+1
=28+70+1
=99

Answer: R=\binom{n}{2}+\binom{n}{4}+1.

Advertisements

About mvtrinh

Retired high school math teacher.
This entry was posted in Problem solving and tagged , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s