I am reading about the problem of cutting/coloring a plane using 2 colors black/white. The problem states:

A number of straight lines are drawn across a piece of paper and each line extends all the way from one border to another. As a result the paper is divided into regions. Show that it is possible to color each region black or white so that no adjacent regions have the same color

The proof is given using induction on the number of lines and inversion of colors of one of the segments created per new line and is understood.
What I don't understand is the following.
The proof states that (emphasis mine):

The requirement for the solution is that the lines are straight i.e. intersect in a single point. If the lines are not straight and the intersect in a segment of a line, inverting the colors of one of the two regions does not guarantee that the coloring of adjacent regions at the boundary of the left and right regions is satisfactory.

What is meant by lines intersecting in a segment of a line? Trying it out with 2 lines that are curved and intersecting in 2 points it seems the solution would still hold. So does it mean the lines are overlapping?

  • 1
    $\begingroup$ The passage may mean that the problematic "lines" are polygonal paths that share a common segment. $\endgroup$
    – Blue
    Dec 29 '20 at 16:36

The problem is if the line segments overlap in some configuration that is more than just a finite set of distinct points:

enter image description here

In this image, the blue and red curves overlap along the purple segment, forming 4 regions which cannot be colored in the desired manner.

  • $\begingroup$ Yes I can see the issue. The colors in the regions adjacent to the overlapping segment are different so the solution will fail. Is it usual to call the overlapping lines as "lines intersecting in a segment"? $\endgroup$
    – Jim
    Dec 29 '20 at 22:15
  • $\begingroup$ It's a little strange to call them "lines" at all, since they aren't straight; I don't know of standard terminology for this sort of intersection. $\endgroup$ Dec 29 '20 at 22:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.