Circle ChordsDate: Fri, 4 Nov 1994 17:56:30 -0500 From: Keroppi Chan Subject: Please help! Hi Dr. Math, I have a math problem. Would you help me? Place n distinct points on the circumference of a circle and draw all possible chords through pairs of these points. Assume that no three of these chords pass through the same point. Find and solve the recurrence relation for the number of interior intersection points formed inside the circle. Thank you very much! Cheers, Keroppi Date: Tue, 8 Nov 1994 13:29:56 -0500 From: Lynn Stallings Subject: Some data on circle chord problem (Keroppi, I posted your question publicly and here's the first response. -- Steve) PROBLEM: >(1) Place n distinct points on the circumference of a circle and draw all >possible chords through pairs of these points. Assume that no three of >these chords pass through the same point. Find and solve the recurrence >relation for the number of interior intersection points formed inside the >circle. I've restricted myself to n evenly spaced points on the circumference of the circle and come up with the following: number of points intersection points interior regions .....2...........................0.....................2 .....3...........................0.....................4 .....4...........................1.....................8 .....5...........................6....................16 .....6..........................13*...................30 .....7..........................35....................56 .....8..........................49**..................88 * includes one w/ 3 chords passing thru 1 intersection point ** includes one w/ 4 chords passing thru 1 intersection point and one with w/ 8 chords passing thru 1 intersection point Date: Tue, 8 Nov 1994 22:40:06 -0500 From: John Conway Subject: Re: Some data on circle chord problem The number of interior intersection points is n-choose-4, since the two lines that define any such point have a total of 4 ends, and any set of 4 points are the ends of just one pair of intersecting lines. This doesn't seem to agree with your figures, so one of us is probably doing something wrong, but I send this note on anyway. I THOUGHT that the number of regions the circle is cut into was the sum of the first 4 or 5 binomial coefficients from the "n" row, but this also seems to be wrong. I'll think again on this! John Conway Date: Tue, 8 Nov 1994 22:40:12 -0500 From: Tom Kilkelly Subject: Re: Recurrence relations and circle chords points chords interior pts n C(n) I(n) 1 0 0 2 1 0 3 3 0 4 6 1 5 10 5 6 15 15 7 21 35 8 28 70 Recursively: C[n] = C[n-1] + n -1 and I[n] = I[n-1] + (n^3 - 6n^2 + 11n - 6)/6 Explicitly: C[n] = n(n-1)/2 and I[n] = (n^4 - 6n^3 + 11n^2 - 6n)/24 Tom Kilkelly St. Thomas Academy Date: Wed, 9 Nov 1994 21:33:18 -0500 From: Stephen B Maurer Let me give a hint . Start with a standard technique: ask a simpler question. How many *chords* are generated by n points on a circle? Answer: n choose 2, because each pair of points generates one chord. So there is a one-to-one correspondence between pairs of points on the circle and chords. Now we ask: what sorts of sets of points on the circle generate interior intersection points? Well, each intersection point is generated by two chords. How many points on the circle generate those two chords? If you finish this approach, you will get a formula for the number of interior intersection points *without* getting a recurrence first. You can use the same methods to get a recurrence *afterward*, but this seems like unnecessary work. Stephen B Maurer Professor of Mathematics Swarthmore College Date: Sat, 12 Nov 1994 07:28:27 -0500 From: North Buncombe High Schl Subject: Re: Recurrence relations and circle chords This is a quartic nth term expression. Try using the ti-82 and its statistics capabilities...it gives you a nice quartic expression using quartic regression (curve fitting). Also, notice the odd/evenness of the terms of the sequence. From: Tom Kilkelly Subject: Re: Recurrence relations and circle chords Dear Doctor Ken, It was great fun communicating about the number of interior points formed by chords connecting n points on a circle. So far I have five completely different formulas that all work! A[n] =3D A[n-1] + (n^3 - 6n^2 + 11n - 6)/6 A[n] =3D (n^4 - 6n^3 + 11n^2 - 6n)/24 A[n] =3D 2A[n-1] - A[n-2] + =85i where i =3D 1..(n-3) A[n] =3D (n/4)* C(n-1,n-4) A[n] =3D n*A[n-1]/(n-4) As you've probably gathered I really enjoy recursion-type problems, so if any good recursion problems come your way, I'd greatly appreciate receiving them. Ciao! Tom Kilkelly St. Thomas Academy |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/