Chess Board Coloring of a Paper using an Arbitrary Curve

Question

Pick a piece of paper and a pen. Put the pen on a starting point and begin to draw an arbitrary curve and don't withdraw your hand until you reached the starting point. You can meet your curve during drawing in some one point intersections but not more (like a line intersection). For example the left curve is allowed but the right one is not.

Now your paper is divided to some areas. We call two areas "neighbors" if their common borderline has more than one point. A "coloring" for the areas of the paper is such that two neighbor areas have different colors. Recall the chess board coloring.

Question: Is it true that there is a $2$-coloring (Black and White) for the areas of a paper when we draw an arbitrary curve on it as described above? If yes, why?

An Example: Note to the coloring in the following shape. You can try on more complicated shapes by your own. It seems to be always true that we can do this by $2$ colors.

Answer 1

Probably. We can create a graph $G$ from the drawing by assigning each region to be colored a vertex. Then if $u$ and $v$ are vertices of $G$, $(u,v)$ is an edge if and only if the regions represented by $u$ and $v$ share a face.

This should result in a bipartite graph which is always two colorable, which in turn implies your picture is two colorable.

The only thing you will have to prove is that $G$ is bipartite. But that shouldn't be too difficult.

Answer 2

If the curve is smooth enough, and there are finitely many self-intersections, the answer is yes. For this answer, I'm going to limit myself to a particular class of curves, though: those where at most two bits of curve intersect at any crossing, so you can have something that locally looks like $\times$, but not something that looks locally like an asterisk (*).

Why the smoothness and finiteness requirements?

If you think of, say, the graph of $x^2 \sin \frac{1}{x}$, between $-1$ and $1$, together with the segment of the $x$-axis between $-1$ and $1$, and connect the two ends with vertical segments, you get something with infinitely many regions, and it gets tough to say whether it's really chess-board-like.

For the case I mentioned, here's a "proof": pick a direction $v$ with the properties that

1. the tangent to your curve is in direction $v$ only finitely often, and

2. at these tangencies, the curve lies on one side of $v$ or the other (i.e., no "inflections" at points where the tangent is $v$).

3. Furthermore, at each crossing, neither tangent vector should be $v$.

4. All lines in direction $v$ intersect the curve in at most finitely many points.

5. Finally, the ray between any two crossing points or any two tangents should not be parallel to $v$.

I'm using smoothness in a big way here. [The existence of $v$ is guaranteed by Sard's Theorem, which is not an easy theorem at all, and I'm not going to prove it here.]

Rotate things so that $v$ is the positive $x$ direction.

From each point in your curve-complement, draw a ray in the positive-$x$ direction. Count the number of intersections of this ray with your curve. If it's odd, color the square black; otherwise color it white. Don't count "tangent" intersections, or crossings. That gives a coloring scheme; the only remaining question is "is it checkerboard-like?".

A "sweep-line" argument takes care of this: consider the coloring of two very nearby points in a region. Are they the same? Compare their ray-curve intersections: if the points are close enough, the ray-curve intersections are pairwise close to each other, and you're good...except in two cases:

1. One ray is tangent to the curve and the other is not. Then the intersection count for the second ray is either two greater than for the first, or equal to it, as the second ray either intersection the curve near the tangency twice or not at all (by the requirement that the curve lie entirely on one side of its tangent line, i.e, condition 2). (I'm using condition 5 to ensure that the ray is tangent to the curve at only ONE point so that this analysis makes sense)

2. The two rays have a crossing between them. This doesn't actually cause a problem, as the intersection of ray1 with the crossing parts can be paired up with the intersections of ray2 with the crossing parts. (The details for this part use property 3 and property 5)

So evidently a connected region has locally-constant color, hence constant color.

Clearly if two regions share a boundary (they're "neighboring countries") then their intersection-counts will differ in parity: A right-pointing ray from a point near the boundary between the left country and the right country will pass through that boundary; for a point just on the other side of that boundary (such a point exists by condition 4), the right-pointing ray will lack that intersection.

In short: even stating the claim really clearly isn't all that easy, and the proof isn't trivial either. It's somewhat simpler if you're willing to say that your curve is a (possibly self-intersecting) polygon with finitely many vertices (i.e., a "connect the dots drawing"); in that case, the conditions I wrote above are all easy to verify.

I believe that there's a one-liner proof using Alexander duality and mod-2 homology/cohomology, but that's not very illuminating, and there's a ton of machinery behind it.

Answer 3

Colour a point black if the winding number of the curve around the point is odd.