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.