I am self-studying Discrete Mathematics, and there is the following exercise. (in Portuguese)
A plane is divided by many lines. Show that it is possible to color
the regions formed with only two colors so that no two adjacent
regions share the same color.
First of all, I was not able to solve it. Then I did I search on Google, and I've find the following here.
4.Show that if n lines are drawn on the plane so that none of them are parallel, and so that no three
lines intersect at a point, then the plane is divided by those lines into $\dfrac{n^{2} + n + 2}{2}$ regions.
The next exercise is:
- Show that if the same lines as in problem $4$ are drawn on a plane that it is possible to color the regions formed with only two colors so that no two adjacent regions share the same color.
Proof: With zero lines, you can obviously do it; in fact, one color would be sufficient. If you can
successfully $2$-color the plane with $k$ lines, when you add the $(k + 1)$st line, swap the colors of all the regions on one side of the line. This will provide a $2$-coloring of the configuration with $k + 1$ lines. (In fact, for this problem, there is no real need to have the lines in general position: some can be parallel, and multiple lines can pass through a point, and the proof will continue to work.)
I did a drawn, and I got convinced, but I did not understand it. I am feeling stupid, but I was not able to understand the proof without drawing.
I would appreciate your help.
Best Answer
I will try to explain the proof you have found instead of giving another one.
The proof is, in fact, by induction. You start with one line and two regions: one black and one white. We want to show that if we have already drawn $k$ lines and painted all regions such that no two adjacent regions share the same color, then we can add any new $(k+1)$th line and repaint some regions (newly created and old ones) such that the property holds: no two adjacent regions share the same color.
Draw a new line, and do NOT change any colors for now. Consider both sides of the new line. No two regions on the same side of the new line are painted same color! This is because you did not change any colors, and any two regions on the same side may share only a part of a line which they shared before you drew a new line. Moreover, if you invert the colors of all regions on same side of the new line, then this property will still hold for them (blacks become white, and whites become black).
When you draw a new line, you create new regions by dividing some regions in two parts. These and only these newly created adjacent regions will share same color. But once you invert the colors of all regions on one side, you get what you need. All adjacent regions on either side are still painted in different colors, and now newly created adjacent regions (which share the same side which is a part of the new line) are opposite colors as well, because one of them got inverted.