# 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

• Adjacent regions with L as their common boundary now have different colors.
• Regions on the un-altered side of L have the colors they had before, so adjacent regions on this side have different colors.
• Regions on the altered side of L have exactly the opposite colors they had before, so adjacent regions on this side have different colors.

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.