How Many Regions are Generated?Date: 05/29/2003 at 17:21:17 From: Sam Subject: Discrete Math Draw a circle and pick n points on it. Now join every point to every other point and suppose that the points have been picked so that no three chords go through one point (i.e. every intersection is the intersection of exactly two chords). How many domains are generated? The points on the circle can't be at even intervals. Date: 05/29/2003 at 17:38:56 From: Doctor Anthony Subject: Re: Discrete Math With no lines the circle has just one region. Now consider any collection of lines. If you draw a new line across the circle that does not cross any existing lines, then the effect is to increase the number of regions by one. In addition, every time a new line crosses an existing line inside the circle the number of regions is increased by one again. So in any such arrangement number of regions = 1 + number of lines + number of interior intersections = 1 + C(n,2) + C(n,4) Note that the number of lines is the number of ways two points can be chosen from n points = C(n,2). Also, the number of interior intersections is the number of quadrilaterals ( = C(n,4)) that can be formed from n points, since each quadrilateral produces just one intersection where the diagonals of the quadrilateral intersect. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/