nathanb <nathanbforrest@gmail.com> wrote: > If I choose 10 points on a circle and join each pair of points with a > chord, it forms a convex 10-sided polygon together with all of its > diagonals. What is the MAXIMUM number of regions formed inside the > decagon by all these chords? 256 regions For more information, see <http://www.research.att.com/~njas/sequences/A000127>. David

"G.E. Ivey" <george.ivey@gallaudet.edu> wrote: > > If I choose 10 points on a circle and join each pair > > of points with a chord, it forms a convex 10-sided > > polygon together with all of its diagonals. What is > > the MAXIMUM number of regions formed inside the > > decagon by all these chords? > This is the old "lost area" problem. It is easy to see that if you > have 1 point are no chords and 1 region; 2 points, 2 regions; 3 > points, 4 regions (the chords form a triangle:1 region inside the > triangle, 3 outside); 4 points, 8 regions (you have a quadrilateral > crossed by its diagonals: 4 regions inside the quadrilateral, 4 > outside); 5 points 16, regions. It looks like "powers of two" but > if you draw the next example carefully, you find that 6 points gives > 31 regions, not 32. > > The correct formula is "Sum (i= 0 to 4) iC(n-1)" where n is the > number of points and iCn is the binomial coefficient n!/(i!(n-i)!), > taken to be 0 if i> n. As long as n< 6, this is the sum of all the > binomial coefficients from 0 to n-1 and so is (1+1)^(n-1)= 2^(n-1). But > for n= 6, it is the sum from 0 to 4 of iC5 and so includes all but 5C5= > 1- it is 1+ 5+ 10+ 10+ 5= 31. For n= 7 it is 1+ 6+ 15+ 20+ 15= 57, just > 6+ 1= 7 less than 2[sup]6[/sup]= 64: 64- 7=57. > For n= 10, this is Sum (i=0 to 4) iC9 which is 0C9+ 1C9+ 2C9+ 3C9+ 4C9= > 1+ 9+ 36+ 84+ 126= 256, exactly what David Cantrell said! And it > happens to be a power of 2- I had thought that Mr. Cantrell had made > the mistake of thinking this was always powers of 2 but, in fact, he > knew exactly what he was doing! If I'd thought, incorrectly, that the formula were 2^(n-1), then I would have said that there should be 512, rather than 256, regions. It is curious that we get a power of 2 for n = 10. Is there some n > 10 for which the number of regions is again a power of 2? I doubt so. David