Two or more spots are placed anywhere on a circle's circumference. Every pair is joined by a straight line. Given n spots, what is the maximum number of regions into which the circle can be divided?

Two points will allow two regions.

Three points will produce a triangle surrounded by three segments of the circle, making 4 regions in all.

Four points will produce a quadrilateral divided into four triangles and there will be four surrounding segments of the circle, for 8 regions in all.

Five points will produce a pentagon with a pentagram internal to it, and five segments of the circle around the pentagon. The five segments, plus five triangles inside the pentagon but outside the pentagram, plus five points of the pentagram, plus the central pentagon inside the pentagram, make 16 regions altogether.

Expanding to six points introduces a couple of novelties.  Starting with six equally spaced points, you get a star of David. This has the lines connecting alternate points. Connecting points on the outside (adjacent points), as before introduces segments of the circle and triangles outside the star but inside the hexagon.  But this time there are also major diagonals to be connected. These divide the six triangular points of the star into two right triangles apiece, and divide the center hexagon into six pieces. Counting these all up, we get 30 regions.  However, there's something we can do here we couldn't do before: make the figure irregular. By pushing one adjacent pair of points apart, their major diagonals' meeting point is pushed toward the opposite side, forming a new triangle (a 31st region) near the center.

So six points still breaks the cycle of 2^(n-1) but also requires irregular spacing of the points to get the maximum number of regions.

Looking up the sequence 2,4,8,16,31 in Sloane's online encyclopedia of integer sequences gives http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eismum.cgi, where a formula is found: C(n,4)+C(n,2)+1 or C(n,4)+C(n-1,2)+n. A reference is also given to a couple of Martin Gardner's books, in one of which (Mathematical Circus) is the latter formula, and a breakdown into a polynomial: (n^4 - 6n^3 + 23n^2 - 18n + 24)/24.

Posted by Charlie on 2004-12-27 20:26:45