A circle where every chord intersects every other chord?

gsingh2011

I'm trying to do a project that requires me construct a circle with n chords. I need to find the maximum number of regions are obtained. I believe the way to do this is to have every new chord intersect every other chord without three chords intersecting at one point. In other words: is it possible to construct a circle such that all of the chords intersect with each other, there exists a new chord that will intersect each other chord, and no more than two chords are concurrent? After trying some small cases, it seems to me that when I do this, n regions are added to the previous region count. In other words, if f(n) is the maximum number of regions given n chords, then f(n) = n + f(n-1). The problem is I need to prove that n regions are added every time. Any hints are appreciated!

quasar987

Well, say you have a circle with r distinct chords in it. And say you have proven that it is possible to draw a chord that intersects all r of them. Follow that r+1 th chord. It starts from the edge of the circle and then enters a region R1. As it crosses the first line L1, it divides R1 in 2. Then the chord enters another region R2 and when it reaches the second line L2, it divides R2 in 2, etc. until it crosses the rth chord and enters a region R(r+1), which it divides in 2 as it reaches the other end of the circle. So, how many new regions were created as a result of this expedition?

gsingh2011

Ok, so the r+1 chord creates r+1 new regions? How do I show that it is possible to draw a chord that intersects the previous r chords?

csco

Take 3 chords that form a right triangle and intersect with each other in the circumference then if you add a new chord that intersects them you will necessarily have a triple intersection right? Ignoring that degenerate case in which chords intersect in the circumference this seems to be true but not trivial to prove. Try to give a proof for the cases n = 4 and n = 5 first and maybe you find a proof for the general case.

quasar987

This is proved by induction. It is obvious for r=1. Now assume it is true for r-1, and consider a circle with r chords each intersecting one another.

First rotate the circle about its center until none of the r chords are horizontal. Then, sweep the circle with a horizontal chord. What will happen? It will eventually encounter a chord, say C1. Continue sweeping. It will encounter a second chord, C2. And by the time this happens, the horizontal chord still intersects chord C1, otherwise it means we have swept chord C1 entirely without encountering chord C2! This is in contradiction with our induction hypothesis that every chord intersects each other ones.

Complete the proof.

gsingh2011

By sweep you mean draw right? And I understand what you're saying, but why would having this new chord not intersect C1 and C2 lead to a contradiction?

quasar987

No, I mean take a straw, or any other long thin object resembling a line, put it on the table just below your circle in a horizontal position and start moving the straw up (that it, sweep the circle from bottom to top.)

If by the time the new chord C intersects C2 for the first time, C no longer intersect C1, then it means that C has swept over the whole of C1 without intersecting C2. But C1 is supposed to intersect C2, so C should have intersected C1 and C2 simultaneously at some point.

gsingh2011

Ok, thanks, I think I should be able to figure it out now.

quasar987

Good luck!