Put n points on a circle and connect each point to every other point by straight lines so as to form the maximum number of regions.

geometry/circle.regions New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

Put n points on a circle and connect each point to every other point by
straight lines so as to form the maximum number of regions.  Find the
formula for the resulting sequence 1, 2, 4, 8, 16, 31, ...

> The sequence 1,2,4,8,16,31,... is created by taking a circle and
> putting n points on the circle and connecting each point to every
> other point by straight lines to form the maximum number of regions.

> Any suggestions on determining the formula that will produce this
> sequence?

-- Black Tiger <blktiger@usis.com>, March 1995

ObPuzzle: Put N points on a sphere, and cut the interior with every
plane determined by three of the points.  What is the maximum number
of interior regions?

-- Dan Hoey <Hoey@AIC.NRL.Navy.Mil>

Show solution

Sure, it's C(N,0) + C(N,2) + C(N,4).

    C(N,0) is 1, because you start out with one region,

    C(N,2) is the number of lines, because you add a region every time
           you draw a line, and

    C(N,4) is the number of intersections, because you add a region
           every time the interior of two lines intersect.

That also explains why it starts out looking like 2^(N-1).

ObPuzzle: Put N points on a sphere, and cut the interior with every
          plane determined by three of the points.  What is the
          maximum number of interior regions?

-- Dan Hoey <Hoey@AIC.NRL.Navy.Mil>, March 1995

[ Editor: no answer to the sphere question was found in the collected
postings. ]