From: Rob Freeth Newsgroups: sci.math Subject: A counting problem..... Date: 23 Apr 1995 12:50:23 GMT Anyone out there able to help? Problem: Draw n points on the circumference of a circle. Join every point to every other point, thus dividing the circle into a number of regions. What is the number N of regions formed? Case 1: Assume the points are arranged so that no three lines meet at an interior point. Hint: For n= 2,3,4,5,6,7,8,.... the sequence is N= 2,4,8,16,31,57,99,163,256,386,562,... There is a simple formula and proof for this case, which I will post if someone else doesn't. Case 2: This is the one I can't solve :( Assume the points are equally spaced on the ciurcumference of the circle, forming a regular n-gon. Note: For n odd, the results are as in Case 1. By observation, the sequence appears to be N= 2,4,8,16,30,57,88,163,230,386,456,... (for n=18, N=2484) What is the formula? Rob Freeth freethr@acslink.net.au ============================================================================== From: gerry@macadam.mpce.mq.edu.au (Gerry Myerson) Newsgroups: sci.math Subject: Re: A counting problem..... Date: 23 Apr 1995 20:59:25 -0500 This problem is solved in Bjorn Poonen and Michael Rubinstein, The number of intersection points made by the diagonals of a regular polygon. The paper isn't published yet, but I expect preprints are available from the authors. The formula is more complicated than anything I want to type in here. Suffice it to say that it depends on the residue class of n (mod 2520). The preprint also gives a history of the problem. An answer was published by Bol, in Dutch, in 1936, but he got some coefficients wrong. A useful reference is J. F. Rigby, Multiple intersections of diagonals of regular polygons, and related topics, Geom. Dedicata 9 (1980) 207--238. Gerry Myerson (gerry@mpce.mq.edu.au) Original post, lightly edited, follows. In article <3ndief$q1a@dingo.cc.uq.oz.au>, Rob Freeth wrote: => => Problem: Draw n points on the circumference of a circle. => Join every point to every other point, thus dividing the circle into => a number of regions. What is the number N of regions formed? => => Case 2: This is the one I can't solve :( => Assume the points are equally spaced on the ciurcumference => of the circle, forming a regular n-gon. => => Note: For n odd, the results are as in Case 1. => => By observation, the sequence appears to be => N= 2,4,8,16,30,57,88,163,230,386,456,... (for n=18, N=2484) => => What is the formula?