Induction Problem 2

Solution

Proof by induction on n (i.e. the number of lines).

Base case: For n = 1, there is exactly one line dividing the plane; we can color one side of it red and the other side green.

Inductive hypothesis: Suppose that we can color the regions created by n lines with two colors, for \(n=1,\ldots,k\).

Rest of inductive Step:

Suppose that we are given k+1 lines in general position. Pick an arbitrary line L and remove it. By the inductive hypothesis, we can find a coloring for the regions formed by the remaining lines in which adjacent regions always have different colors.

Now, add L back. Notice that the only regions that are affected by this addition are the ones which are split by L. To fix this, select one side of the line L, and swap the color of every region on this side. See this picture

Notice that

So we have a coloring of the regions formed by our k+1 lines, in which adjacent regions have different colors.

Self-check

Your proof should be mostly talking about the geometrical situation, i.e. the lines, the regions, the colors. It should have few (if any) equations.

Did you explain specifically how to modify the region coloring when you added the new line? Make it explicit enough that your roommate studying history could follow the procedure.