Go back to previous page
Forum URL: http://www.cut-the-knot.org/cgi-bin/dcforum/forumctk.cgi
Forum Name: College math
Topic ID: 546
Message ID: 9
#9, RE: difficult sequence, areas partitioned in circle ,
Posted by mpdlc on Dec-21-05 at 11:05 AM
In response to message #8
Hi Tommy,

Not willing to pose a question and later not answering it and as a follow-up of my remarks, I must add the following.

My proposal was to get the maximum number of regions that we can form taking the N points p1, p2.....pN within a circle (C), and connecting them with circumferences.
All circumferences will contain the center O of the original circle (C), and any pair of points: ( Op1p2; Op1p3; ...Op1pN,...Op2p3,Op2p4...Op(N-1)p(N) ).

This problem come out to be the same as getting the maximum amount of regions it can be form by laying in a plane N straight line, since by virtue of an inversion using as circle of inversion (C) the circumferences all containing the center O will been transformed in straight lines not passing by O.
Therefore is the same problem that Stuart suggested in the last paragraph of his remarks. Obviously calling N the number of straight lines, N equals to n(n-1)/2, being n the number of points. So if you are still interested the answer follows below.

I do remember from my late HS year to been taught how to solved this problem by induction using the formulae for arithmetic progression of a second order is elegant and can be extrapolated to the maximum number of regions that can be divided a
nD space by hyper-planes, I believe the method belongs to Professor Polya. Obviously it will include the division of a 3D space using planes which is known by Steiner�s problem and which is referred in article 67 of Heinrich Dorrie book, as a preliminary problem the article solves the division of the plane by N straight lines.

http://www.cut-the-knot.org/books/dorrie/content.shtml


Since the explanation by arithmetic progression of a second order require using combinatory notation, and my word processor is not fitted for the job, I will just summarize synthetically the content of the article referred to our case.

Assuming that our plane is divided by N lines in R(N) regions if we draw an additional line, this particular line not being parallel to any of the existing ones will cut the N existing lines in N points and thus will transverse N+1 of all existing regions, those regions will become divided in two parts, so the new number of region R(N+1) will obey the difference equation:

R(N+1) = R(N) + (N+1) which is easily solved as follow :

R(1) = 1 +1
R(2) = R(1) +2
R(3) = R(2) +3
.....

R(N) = R(N-1) +N

The addition of the above will yield to: R(N) = 1 + ( 1+2+3+�+N) and therefore

R(N) = 1 + N( N+1)/2.

So since N=n(n-1)/2 all we have to do is to substitute N in term of n if our data are the number of points.