# Intersection Points in a Circle

• Dec 6th 2009, 06:33 PM
zachsch
Intersection Points in a Circle
A chord is drawn between every two point on the perimeter of a circle. There are n points on the perimeter. Every two chords intersect at a point either on the perimeter or inside the circle.

(a) Determine the number of chords drawn

-- (n choose 2)

(b) What is the maximum number of intersection points inside the circle?

-- For this one I keep ending up in an infinite loop and drawing increasingly harder circles. Can someone point me in the correct direction?

I have (n*(n-1)) + (n-3)n - n + (n-4)n - n....

I don't know how to show when to stop.

(c) What is the maximum number of chords which can go through any single intersection point inside the circle?

--I don't even know where to begin here.

Any help would be greatly appreciated!!!
• Dec 7th 2009, 03:44 PM
gmatt
Quote:

Originally Posted by zachsch
A chord is drawn between every two point on the perimeter of a circle. There are n points on the perimeter. Every two chords intersect at a point either on the perimeter or inside the circle.

(a) Determine the number of chords drawn

-- (n choose 2)

(b) What is the maximum number of intersection points inside the circle?

-- For this one I keep ending up in an infinite loop and drawing increasingly harder circles. Can someone point me in the correct direction?

I have (n*(n-1)) + (n-3)n - n + (n-4)n - n....

I don't know how to show when to stop.

(c) What is the maximum number of chords which can go through any single intersection point inside the circle?

--I don't even know where to begin here.

Any help would be greatly appreciated!!!

You got a right.

b ) is a bit tricky. You have to use a counting trick. Consider any two points A,B along the circle. Then the chord AB splits the circle into a minor arc and a major arc (that is a bigger arc and a smaller arc.) The only chords that intersect AB inside the circle are coords that are formed by one point on the major arc and one point on the minor arc. If there are k points on the minor arc, there are k(n-2-k) chords that can be formed that will intersect AB inside the circle.

This implies that the total number of intersections inside the circle are at most:

$\sum _{k=0} ^{n-2} k (n-2-k) = \sum _{k=0} ^{n-2} k (n-2) - \sum _{k=0} ^{n-2} k^2 = \frac{(n-2)^2 (n-1)}{2} - \frac { (n-2)(n-1)(2n-3)}{6}$ you can simplify it further.

c) this is easy; you just need to make the following observation, if two chords share the same two endpoints it is the same chord. If two chords share one endpoint, they have to intersect on the circle and can not possibly intersect in the same point INSIDE the circle. Since you can not reuse one point to make multiple chords that will go through the same intersection point inside the circle, this means that at most $\lfloor n/2 \rfloor$ chords can intersect in the same point inside the circle.
• Dec 7th 2009, 04:16 PM
zachsch
Thank you so much!

Can you just clarify where you got "k(n-2-k)" from in part b? I'm pretty much good until then.

Thanks
• Dec 7th 2009, 04:26 PM
gmatt
Think about it carefully, you have points A, B. Then on the minor arc there are k points between A and B. That means there are n -2 -k points on the major arc. Now you can pair each of the points on the minor arc with each of the points on the major arc, yeilding k (n-2-k) possible chords
.
• Dec 7th 2009, 04:27 PM
zachsch
Ah ha. Thank youu!
• Dec 7th 2009, 04:53 PM
Plato
Quote:

Originally Posted by gmatt
This implies that the total number of intersections inside the circle are at most:
$\sum _{k=0} ^{n-2} k (n-2-k) = \sum _{k=0} ^{n-2} k (n-2) - \sum _{k=0} ^{n-2} k^2 = \frac{(n-2)^2 (n-1)}{2} - \frac { (n-2)(n-1)(2n-3)}{6}$ you can simplify it further.

gmatt.
Does your formula work for n=5 or n=6?
I think not. It gives 4 for n=5. The correct answer is 5.
The case for n=6 is easy to draw also.
Now maybe I have missread the question?
• Dec 7th 2009, 05:15 PM
gmatt
Quote:

Originally Posted by Plato
gmatt.
Does your formula work for n=5 or n=6?
I think not. It gives 4 for n=5. The correct answer is 5.
The case for n=6 is easy to draw also.
Now maybe I have missread the question?

well spoted!

ahh ok, I am missing a important part, I'll add it in a bit.
• Dec 7th 2009, 07:07 PM
zachsch
Should the number include the points where the chords intersect the perimeter?

So for n=3, you have 6 intersection points?

"Every two chords intersect at a point either on the perimeter or inside the circle."
• Dec 7th 2009, 08:12 PM
gmatt

The actual formula that you want is

$
\sum_ {i=0} ^{(n-2)} \sum _{k=0} ^{(n-2 - i)} k (n-2-k -i)
$

This one is more difficult to simplify, but not impossible. You can try simplifying it using known summation formulas.

All you need is the following formulas to simplify

$\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6} = \frac{n^3}{3} + \frac{n^2}{2} + \frac{n}{6}$

$\sum_{i=1}^n i^3 = \left(\frac{n(n+1)}{2}\right)^2 = \frac{n^4}{4} + \frac{n^3}{2} + \frac{n^2}{4} = \left[\sum_{i=1}^n i\right]^2$
• Dec 7th 2009, 10:02 PM
gmatt
oh, wow. I just plugged in that fancy formula I got into wolfram alpha

.....

$\sum_ {i=0} ^{(n-2)} \sum _{k=0} ^{(n-2 - i)} k (n-2-k -i) = \frac{1}{24}(n-3)(n-2)(n-1)n = \binom{n}{4}$
well that was a fun excercise, I came up with an identity for $\binom {n}{4}$ that is non-trivial.