Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Inductive proof problem

Name: Anonymous 2006-10-29 12:09

Good Anonymouses, this anonymous is having a little trouble with starting this induction proof:

Two non-overlaping circles of radius 1 intersect in exactly two points. Prove by induction that given n >= 2 non-overlapping circles in the plane that the total number of intersections is never more than n(n-1).

I know this is true and I can see why, but I don't know what to do after I've done the base case and the inductive hypothesis.

Name: Anonymous 2006-10-29 15:03

Wouldn't I need to prove that adding a circle to n circles will at most add 2n intersections first before I can use it?
It follows directly from the base case (which you said you already proved, and which is actually what the first sentence of the problem states as a given with the change from >>5). Observe:

You have n circles. You add one. The intersections between the n circles won't change, but the added circle can make at most 2 more intersections with each of the n circles, hence at most 2n intersections are added.

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List