Newsgroups: sci.math, rec.puzzles
Followup-To: rec.puzzles
From: hoey@aic.nrl.navy.mil (Dan Hoey)
Date: 07 Mar 1995 22:14:13 GMT
Subject: Re: Sequence Problem

blkti...@usis.com (Black Tiger) writes:

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

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@AIC.NRL.Navy.Mil