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?