Number of Regions in a Convex PolygonDate: 04/29/2008 at 16:20:35 From: Fernando Subject: Number of regions in a convex polygon How many regions is a convex polygon divided into by its diagonals, if no three are concurrent? The solution is nC4 + (n-1)C2 for n >= 4. What is the meaning of this solution? Why are no three diagonals concurrent? Date: 05/02/2008 at 20:29:19 From: Doctor Jordan Subject: Re: Number of regions in a convex polygon Hi Fernando, For a convex n-gon with vertices A_1,A_2,...,A_n, such that when all the vertices are joined by diagonals no three diagonals intersect at a single point in the interior of the n-gon, let f(n) be the number of regions in the n-gon. We will find a recurrence relation for f(n), and when we solve the recurrence relation we will find that f(n) = C(n,4) + C(n-1,2) where C(i,j) is i choose j. Indeed there are some convex n-gons where three diagonals will intersect at a single point, but we are only considering the convex n-gons where this does not happen. It is not obvious that these exist, but we are assuming they do for this question. Let us add a vertex A_{n+1} to get a convex (n+1)-gon such that when all the vertices are joined by diagonals no three diagonals intersect at a single point in the interior of the (n+1)-gon. For each k=2,3,...,n-1, the diagonal from A_{n+1} to A_k is intersected by the diagonals from the vertices A_1,...,A_{k-1} to the vertices A_{k+1},...,A_n. There will be (k-1)*(n-k) points of intersection on the diagonal A_{n+1}A_k, which will divide it into (k-1)*(n-k)+1 segments. Each of these segments adds 1 region; you might need to draw a few examples to see this. Furthermore, if we ignore the diagonals that include the point A_{n+1}, there are f(n)+1 regions, since we have all the regions that were in the n-gon, and the new triangle with vertices A_1, A_{n+1} and A_n. Therefore f(n+1) = f(n) + 1 + sum_{k=2}^{n-1} ((k-1)(n-k)+1). It takes a few lines but we work this out and get f(n) + (n-1) + C(n,3). Play around with this a bit more to find f(n) = C(n,4) + C(n-1,2). This solution follows the one on p.p. 249-250 of "Counting and Configurations: Problems in Combinatorics, Arithmetic, and Geometry" by Jiri Herman, Radan Kucera, Jaromír Šimša, and Karl Dikher. It took me a while for this argument to make sense. Please spend time thinking about it, and maybe draw the convex 5-gon and convex 6-gon. If it still doesn't make sense please write back. - Doctor Jordan, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/