Two Color Coloring of the Plane: What is this about?
A Mathematical Droodle
(The lines in the applet below can be dragged or rotated around their endpoints if they are dragged near the opposite endpoint. Try it. - However, the applet is (I hope temporarily, is out of order, due to the browsers having stopped to support Java))
The applet may suggest the following statement:
The design obtained by cutting the plane with straight lines can be colored with just two colors so that no two regions that share a side are of the same color.
You may want to check that this is indeed so:
Why is it indeed possible to use just two colors?
Start with the fewest meaningful number of lines. A single line divides the plane into two half-planes; clearly two colors suffice to color the plane: each of the half-planes gets its own color. Note in passing that there are just two possible colorings. One of the half-planes is either white or black whilst the other half is painted with the opposite color.
Now see what happens when you add one line at a time. With each new line we associate an arbitrary manner one of the half-planes it divides the plane into. We'll call it provisionally the line's half-plane. So, when adding a line, leave the colors in its half-plane unchanged but swap all colors in the other half-plane with their opposite colors. Observe that this procedure leads to a two-color coloring of the plane. Indeed, In the line's half-plane where colors have not been changed any two adjacent regions are colored with different colors (for this how they were painted before the last line was drawn.) In the other half-plane this is also true, for changing the colors to their opposites still leaves two adjacent regions painted with different colors (again because this was so before the last line was drawn.) Now, the newly created regions, i.e., the parts of the regions crossed by the last line share a side which is a part of the line; originally, being parts of the same region they were painted with the same color but then the color of one of them has been changed, making them painted in different colors.
What we got is a simple proof by induction: our statement (that the two-color coloring is possible) is obvious for a single line. Also, if it was true for a number of lines, it remains true after one more line is added. Finally, it is worth mentioning that for any configuration of lines there are just two possible ways to paint the plane with two colors such that any two adjacent regions receive different colors. This was true for a single line and remains so, perhaps unexpectedly, for any number of lines. Indeed, we can paint any region with one of the two colors and then proceed (recursively) to paint the adjacent regions appropriately. On any step, the selection of the color for a region is forced by the color of the adjacent region painted on the previous step - it must be different and we do not have many choice, just another color.
- J. Mason, L. Burton, K. Stacey, Thinking Mathematically, Addison-Wesley, 1985