Jump to content
BrainDen.com - Brain Teasers
  • 0

The recurrence relation of the interior of a circle


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.

Share this post

Link to post
Share on other sites

2 answers to this question

  • 0

The total number of intersections for all chords formed by n points on the circle is n(n-1)(n-2)(n-3)/24.

Let's say we have k points and all the chords connecting them. Each point has k-1 chords connecting it to other points. Let's add one more point and count how many new intersections it will produce.

The new point X will be between some other 2 points - let's call them A and B. A and B are the immediate neighbors of X, so the chords AX and BX will not produce any intersections.

Now let's consider the next pair of points C and D that are immediate neighbors of A and B respectively. Chord CX will intersect all chords connecting A with all other points except C and X, so it will produce k-2 intersections. The same is true for the chord DX - it will intersect all chords connecting B with all other points except D and X.

Going to the next pair of points (E and F) and applying the same logic we find that chords EX and FX produce 2*(k-3) intersections each. Then 3*(k-4), etc...

So, the total number of new intersections added by the point X is the sum 1*(k-2)+2*(k-3)+3*(k-4)+...+(k-3)*2+(k-2)*1 or sum[ m*(k-m-1) ] for m in (1..k-2). This sum evaluates to (k-2)*(k-1)*k/6.

So, to determine the total number of intersection produced chords connecting n points on the circle we need to find the sum of these sums with k ranging from 1 to n-1. This sum equates to the answer above.

Share this post

Link to post
Share on other sites
  • 0

For (n+3) points on the circle, number of intersections for chords coming from one of the points equals:

C(n) = 1*n + 2*(n-1) + 3*(n-2) + ... + n*1
Let's call
S(n) = C(n) - C(n-1)
It is easy to see that
S(n) = 1 + 2 + ... + n = n(n+1)/2
C(n) = S(n) + S(n-1) + ... + S(1)
It is a known result that
C(n) = n*(n+1)(n+2)/6
Total number of intersections for (n+3) points equals
(n+3)*C(n)/4 = n*(n+1)(n+2)(n+3)/24

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.