1. Arrangement of Lines

Base case: n = 3. Three lines in general position define three noncolinear points of intersection, forming a single closed region, a triangle.

Induction hypothesis: Suppose the claim is true for n lines. That is, assume that n lines in general position always form at least one triangular region. (A "region" is an area bounded by lines *with no lines crossing through it*, so the claim isn't totally trivial.)

We must now use this hypothesis to show that the claim still holds for n+1 lines. We have n lines, defining at least one triangular region ABC. Add a line L. Two cases: either L crosses ABC, or it doesn't.

If L doesn't cross ABC, ABC is still an unbroken triangular region, and we're done.

If L *does* cross region ABC, it must cross one of ABC's three sides going in, and another going out. (It can't cross through ABC's vertices, because then three lines would be intersecting at a point, contradicting the general position assumption.) WOLOG (without loss of generality), assume it enters through segment AB, crossing at point P, and exits through segment AC, crossing at point Q. Then a new triangular region APQ is formed, and we're done.

So if the claim is true for n, it's true for n+1, and we know it's true for n = 3. So it's true for n >= 3.

This is a good example of a proof which becomes a lot more readable when you give names to things (L, ABC, P, Q).

2. Sum of Squares of First Natural Numbers

It's good to begin by giving some idea of how you arrived at the expression, though for an induction proof this often won't be strictly required. (One way to find it, aside from trial and error, was to assume it was some cubic expression S(n) = an^3 + bn^2 + cn + d, and solve for (a,b,c,d) given that S(n) = S(n-1) + n^2.)

Anyway, the correct expression is: S(n) = (1/3)n^3 + (1/2)n^2 + (1/6)n.

Now the induction.

Base case: n = 1. (1/3)1^3 + (1/2)1^2 + (1/6)1 = 1, which is in fact the sum of the first 1 squares. So far so good.

Induction hypothesis: For a particular n, S(n) = (1/3)n^3 + (1/2)n^2 + (1/6)n.
Need to show from this that S(n+1) = (1/3)(n+1)^3 + (1/2)(n+1)^2 + (1/6)(n+1):

S(n+1) = S(n) + (n+1)^2 (defn of S(n))
= (1/3)n^3 + (1/2)n^2 + (1/6)n + (n+1)^2 (ind hyp)
= (1/3)n^3 + (1/2)n^2 + (1/6)n + n^2 + 2n + 1
= (1/3)n^3 + (3/2)n^2 + (13/6)n + 1

We're trying to show that this is equal to:

(1/3)(n+1)^3 + (1/2)(n+1)^2 + (1/6)(n+1)
= (1/3)n^3 + n^2 + n + 1/3 + (1/2)n^2 + n + 1/2 + (1/6)n + 1/6
= (1/3)n^3 + (3/2)n^2 + (13/6)n + 1

Which it is. So we're done.

3. Circle Map Coloring

base case: n = 0. There's only one region, the entire plane, so we certainly don't need more than two colors.

Now, induction hypothesis: any arrangement of n circles can be 2-colored. Need to use this to show the claim holds for n+1 circles.

We have some 2-coloring with n circles such that no neighboring regions are the same color. How can we maintain this property when we add another circle? It was dangerous to start drawing diagrams, because there are so many different ways n circles can intersect that it's hard to convince the reader that you've covered all the cases.

Better to proceed in general terms. We have n circles, dividing the plane into a number of regions. The boundary of any region is made up of arcs - portions of existing circles. Every arc lies between two regions. Call an arc "valid" if the two regions it separates are different colors, and "invalid" if they're the same color. By the induction hypothesis, all arcs are valid when we have n circles.

Now, suppose we add the (n+1)st circle C without changing the colors of any regions. Which arcs become invalid? The old arcs (portions of the old n circles) remain valid, since the regions they separate remain the same (different) colors. But *every* new arc along the perimeter of C is invalid, because it cuts through an old region which was a single color, and therefore both new regions it separates are the same color.

Thus, the algorithm: switch the color of every region inside C. This makes all the invalid arcs on the perimeter of C valid. Meanwhile, every old arc outside C remains valid, since the regions it separates are unchanged, and every arc inside C remains valid since both regions it separates change colors. All invalid arcs become valid, and all valid arcs remain valid; so after this operation all arcs are valid, and therefore no neighboring regions are the same color.

Some people were confused about the following case. Suppose we have two adjacent circles in the plane touching at a single point. The two circles must be the same color, since each must be the opposite color of the outside region. So, don't they constitute neighboring regions of the same color? The answer is no. Two regions are only neighbors if they share a border. A single point of contact is not a neighboring edge. So it's fine if the two circles are the same color.

4. The Collapsing Compass Computer

1. Draw the line BC.
2. Draw a circle C1 centered at B with radius BC.
3. Draw a cirlce C2 centered at C with radius CB. C1 and C2 intersect at points D and E.
4. Draw the line DE. This cuts line BC at midpoint F.
5. Draw a circle C3 centered at F with radius FA.
6. Draw the line AF, extending it until it cuts the circle C3 on the other side of F. Call this intersection point G.
7. Draw the line CG. This is the solution.

This algorithm requires 7 steps.

Proof of correctness:

Steps 1-4 find the perpendicular bisector of segment BC. Thus segments CF and BF have the same length.

Case 1: If C is NOT on the line passing through AB

We show that triangles ABF and FCG are congruent: angles CFG and BFA are the same. Lengths AF and FG are the same. Thus, by congruent triangles, CG is a translation of AB.

Case 2: If C is on the line passing through AB

Segments AF and FG have the same length, and since the lengths of CF and BF are also equal and A, B, C, G are on the same line, then CG is a translation of AB.

You can check this answer, as well as your own, using Francois Labelle's wonderful on-line java applet for ruler & compass constructions. This can be found at: http://www.cs.mcgill.ca/~sqrt/cons/constructions.html. Set the 'problem' menu in the Applet to: "transfer a distance", and then try to stransfer the segment P1 - P2 to the new point P3.

(Thank you Yufeng Wang for pointing out the difference in the proof for each of the two cases)