From: Fred Galvin
Subject: Re: Polygon Problem Challenge
Date: Fri, 26 Mar 1999 18:28:40 -0600
Newsgroups: sci.math,sci.fractals,comp.graphics.algorithms,comp.arch.arithmetic,comp.graphics.misc,comp.arch.embedded,sci.electronics.cad,comp.cad.i-deas,sci.logic,sci.image.processing,comp.cad.autocad
Keywords: regions formed by diagonals
On Fri, 26 Mar 1999, Mark A. Barclay wrote:
> Here's a puzzle I came up with about 5 years ago. So far nobody has
> provided the correct general solution. It's one of those puzzles that's
> very easily stated yet surprisingly difficult to solve. I presented this
> problem to a bright career mathematician who, after a couple of days,
> gave me a 5 page solution. It was wrong.
>
> Here goes...
>
> =======================================================================
> How many polygons (with non-zero area) result from joining all vertices
> of a regular polygon to all other vertices with straight line segments?
> =======================================================================
> [...]
> In the case of a square, joining all vertices to all other vertices with
> straight line segments results in 4 polygons.
OK, then you want the number of *regions* formed by drawing all the
diagonals in a regular polygon. This is a nontrivial problem! It took 2
mathematicians 22 pages to describe their (computer-aided) solution of
your problem, together with the related problem of counting the number of
points where 2 or more diagonals intersect: Bjorn Poonen and Michael
Rubinstein, The number of intersection points made by the diagonals of a
regular polygon, SIAM j. Discrete Math. 11 (1998), 135-156; see also
.
Here is their formula for the number of regions:
Start with (n^4-6n^3+23n^2-42n+24)/24;
if n is even, subtract (5n^3-42n^2+40n+48)/48;
if n is divisible by 4, subtract 3n/4;
if n is divisible by 6, subtract (53n^2-310n)/12;
if n is divisible by 12, add 49n/2;
if n is divisible by 18, add 32n;
if n is divisible by 24, add 19n;
if n is divisible by 30, subtract 36n;
if n is divisible by 42, subtract 50n;
if n is divisible by 60, subtract 190n;
if n is divisible by 84, subtract 78n;
if n is divisible by 90, subtract 48n;
if n is divisible by 120, subtract 78n;
if n is divisible by 210, subtract 48n.
I hope I got that right! The formula is Theorem 1.2 on p. 137 of the
paper. Anent the history of the formula, the authors say: "The Dutch
mathematician Gerrit Bol...gave a complete solution in 1936, except that a
few of the coefficiants in his formulas are wrong...we relegate much of
the work to the computer, whereas Bol had to enumerate the many cases by
hand. The task is so formidable that it is amazing to us that Bol was able
to complete it, and at the same time not so surprising that it world
contain a few errors!...Bol's work was largely forgotten...Many other
authors in the interim solved special cases of the problem."
On p. 154 of their paper, the authors tabulate the answers to your problem
for values of n from 3 to 30, namely:
1, 4, 11, 24, 50, 80, 154, 220, 375, 444, 781, 952, 1456, 1696, 2500,
2466, 4029, 4500, 6175, 6820, 9086, 9024, 12926, 13988, 17875, 19180,
24129, 21480
==============================================================================
From: "Mark A. Barclay"
Subject: Re: Polygon Problem Challenge
Date: Fri, 26 Mar 1999 22:20:15 -0600
Newsgroups: sci.math,sci.fractals,comp.graphics.algorithms,comp.arch.arithmetic,comp.graphics.misc,comp.arch.embedded,sci.electronics.cad,comp.cad.i-deas,sci.logic,sci.image.processing,comp.cad.autocad
Fred Galvin wrote:
[quoted above -- djr]
Wow, I think you've got it!
I worked on this for days myself (although I'm not a mathematician, but
I couldn't resist it). And the scribblings I ended up with looked very
much like the first two lines (if n is divisible by 6) and I began
drowning in exception cases. I tried to get a hold of the
Poonen/Rubinstein paper but I could only get a postscript copy and I
have no way to read a PostScript file.
I'm going to look closely at the paper if I am finally able to print it
out (I guess I just need a PS printer). Is there any other way I can get
a hold of that paper? Maybe you could send me a copy after I send you
your "trophy" :)
The form of your solution is definitely what I expected to see, and teh
reference to Poonen/Rubinstein's paper confirms to me that your solution
uses the right tools.
CONGRATULATIONS!
To where shall I send the Slide Rule? I hope you put it on display...
Mark A. Barclay
===================================
Work like you don't need the money,
Love like you've never been hurt,
Dance like no one is watching.