Kvant Math Problem 1140

Each intersection point is a crossing of two branches.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m26s
Source on kvant.digital

Problem

Let us draw one or several intersecting curves in the plane (the curves may have self-intersection points; Fig. 1). At each intersection point, one can perform a “reconnection” in either of two ways (Fig. 2). If a reconnection is carried out at every intersection point, the result will be several nonintersecting curves (Fig. 3).

  1. Prove that the number of nonintersecting curves that can result is no greater than the number of regions into which the original curves divide the plane (in Fig. 1 there are 7 such regions).
  2. Is it always possible to perform the reconnections so that the result is a single curve?
  3. Choose an orientation on each curve and perform the reconnections in accordance with these orientations so that the arrows “repel” each other (Fig. 4). Can the result be a single curve?

Fig. 1

Fig. 1

Fig. 2

Fig. 2

Fig. 3

Fig. 3

Fig. 4

Fig. 4

S. L. Tabachnikov

Exploration

Each intersection point is a crossing of two branches. After all crossings are reconnected, every crossing disappears and the picture becomes a disjoint union of simple closed curves. The first question asks for an upper bound on the number of resulting components.

A natural way to relate the resulting curves to the regions of the original arrangement is to look locally at a crossing. Before reconnection there are four sectors around the crossing, belonging to four regions of the complement. After reconnection, the new arc separates two opposite sectors from the other two. Thus each resulting curve should lie along boundaries of regions of the original arrangement.

Consider the planar graph formed by the original curves. Its vertices are the intersection points and its edges are the curve segments between consecutive intersections. Let $V,E,F$ denote the numbers of vertices, edges, and regions. Euler's formula gives

$$V-E+F=1+C,$$

where $C$ is the number of connected components of the graph. Since every vertex has degree $4$,

$$2E=4V,\qquad E=2V.$$

Hence

$$F=V+C.$$

Suppose after reconnection we obtain $k$ disjoint curves. Each reconnection pairs the four half-edges at a vertex. The resulting curves are precisely the circuits of the corresponding pairing. There should be a way to associate to each such circuit a distinct region of the original arrangement. If so, then $k\le F$.

To test whether distinct circuits can correspond to the same region, take a simple figure-eight. There is one crossing, $F=3$. The two possible reconnections produce either one circle or two circles. In the second case the two circles bound the two bounded regions, so distinct circuits indeed correspond to distinct regions.

For the second question, try to obtain one curve. At every crossing there are exactly two pairings. Think of the original arrangement as a connected $4$-regular graph. Choosing a pairing at every vertex produces a decomposition of the edges into circuits. This is the theory of Euler circuits. If the graph is connected, an Euler circuit exists, and at each vertex the two visits of the Euler circuit determine a pairing. Then all edges belong to one circuit after reconnection. If the original arrangement has several connected components, a single curve is impossible because no reconnection can connect different components.

For the third question, the orientation rule is special. At each crossing the pairing is forced. This is the oriented smoothing used in knot theory. The resulting curves inherit orientations.

A useful invariant is the index of a region. Choose a region and define an integer by counting signed crossings of a path from infinity. Adjacent regions differ by $1$. Under the oriented smoothing, every resulting curve is the boundary of a region of constant index. Hence the number of resulting curves equals the number of regions of nonzero index. In particular, there is always at least one outer region of index $0$, so the number of resulting curves is strictly less than $F$.

A single resulting curve would divide the plane into exactly two regions. If the original arrangement has any crossing, there are at least three index levels among regions, so more than one smoothed component appears. Testing the figure-eight confirms this: the oriented smoothing gives two circles, never one.

The delicate point is proving that oriented smoothing can never yield a single curve. The region-index interpretation appears to be the correct mechanism.

Problem Understanding

This is a Type B problem. We must prove an upper bound in part (1), determine when a single curve can be obtained in part (2), and determine whether the orientation-preserving reconnection of part (3) can produce a single curve.

The original curves form a planar $4$-regular graph whose vertices are the intersection points. Reconnecting at each vertex replaces the crossing by one of the two possible pairings of the four incident half-edges. After all reconnections, the graph becomes a disjoint union of nonintersecting closed curves.

The main difficulty is relating the combinatorics of these pairings to the regions of the original arrangement, and then understanding the special oriented pairing of part (3).

The expected answers are that the number of resulting curves never exceeds the number of regions, that a single curve can be obtained exactly when the original arrangement is connected, and that under the orientation rule a single curve cannot occur unless there were no intersections to begin with.

Proof Architecture

Let $G$ be the planar graph formed by the original curves, with vertices at crossings and edges between consecutive crossings.

Lemma 1. Every curve obtained after reconnection has on one side a uniquely determined region of the original arrangement. Sketch: at each smoothed vertex the curve passes between the same pair of local sectors, so one can follow a fixed adjacent region all around the curve.

Lemma 2. Different resulting curves correspond to different regions of the original arrangement. Sketch: if two distinct curves had the same adjacent region, that region's boundary would contain both curves, contradicting connectedness of the boundary component.

Lemma 3. The number of resulting curves is at most the number $F$ of regions. Sketch: combine Lemmas 1 and 2.

Lemma 4. If $G$ is connected, there exists a choice of reconnections yielding a single curve. Sketch: take an Euler circuit of the connected $4$-regular graph and pair half-edges at each vertex according to consecutive passages of that Euler circuit.

Lemma 5. If $G$ is disconnected, a single resulting curve is impossible. Sketch: reconnections do not create edges between distinct connected components.

Lemma 6. Under the oriented smoothing, every resulting curve is the positively oriented boundary of a region of constant index. Sketch: use the standard region-index function; across an oriented edge adjacent indices differ by $1$, and the smoothed curves separate regions of consecutive indices.

Lemma 7. If there is at least one crossing, oriented smoothing produces at least two resulting curves. Sketch: the unbounded region has index $0$, while some region has nonzero index; boundaries between index levels yield at least two components.

The hardest step is Lemma 6, because it requires a precise connection between the orientation rule and the region-index function.

Solution

Let $G$ be the graph obtained from the original system of curves by declaring every intersection point to be a vertex and every arc between consecutive intersections to be an edge. Every vertex of $G$ has degree $4$.

After choosing a reconnection at each vertex, the crossings disappear. The edges of $G$ are not changed; only their incidences at the vertices are changed. Since every new vertex has degree $2$, the resulting graph is a disjoint union of simple closed curves. Let $k$ be the number of these curves.

For the first question, fix one of the resulting curves $\gamma$. Near each former crossing, the smoothing joins two opposite half-edges. Among the four local sectors determined by the crossing, there is a unique sector that stays on the left side of $\gamma$ when $\gamma$ is traversed. Moving along $\gamma$, these local sectors fit together continuously. Hence one and the same region of the original arrangement remains on the left side of $\gamma$ all along the curve.

Thus every resulting curve determines a region of the original arrangement.

Suppose two distinct resulting curves $\gamma_1$ and $\gamma_2$ determined the same region $R$. Then both curves would be boundary components of $R$. Since each resulting curve is a simple closed curve, one of them would lie inside the other. The region between them would then belong to the complement of the original arrangement, contradicting the assumption that both bound the same region $R$. Hence distinct resulting curves determine distinct regions.

We have obtained an injective map from the set of resulting curves to the set of regions of the original arrangement. If $F$ denotes the number of regions, then

$$k\le F.$$

This proves the first statement.

For the second question, first assume that $G$ is connected.

A connected graph all of whose vertices have even degree possesses an Euler circuit. Let

$$e_1,e_2,\dots,e_m,e_1$$

be such a circuit in $G$.

At a vertex $v$, the Euler circuit passes through $v$ twice. Each passage enters along one half-edge and leaves along another. Reconnect the four half-edges at $v$ according to these two passages of the Euler circuit. Doing this at every vertex, the Euler circuit becomes a single closed curve containing every edge of $G$ exactly once.

Hence, when $G$ is connected, one can choose the reconnections so that the result is a single curve.

Now assume that $G$ is disconnected. Reconnection changes only the pairing of half-edges belonging to the same vertex. It never creates an edge joining two different connected components of $G$. Consequently each connected component of $G$ remains isolated from the others after all reconnections. A single resulting curve would have to contain edges from every connected component, which is impossible.

Therefore a single curve can be obtained if and only if the original arrangement is connected.

We turn to the third question.

Choose orientations on the original curves and perform at every crossing the smoothing prescribed in Figure 4. Define an integer-valued function on the regions of the complement as follows. The unbounded region receives index $0$. Whenever two regions share an edge, crossing that edge in the positive normal direction increases the index by $1$. Since every original curve is closed, the total change of index along any closed path is $0$, so the index is well defined.

At an oriented crossing, the four surrounding regions have indices

$$n,\quad n+1,\quad n+1,\quad n+2$$

in cyclic order. The oriented smoothing joins precisely the two branches separating the regions of index $n+1$. Hence every smoothed component runs along the boundary between regions whose indices differ by $1$, with the region of larger index always on the left.

Following such a component all the way around, the region on its left has a constant index. Thus every resulting curve is the positively oriented boundary of a region of positive index.

The unbounded region has index $0$. If the original arrangement contains at least one intersection, then some region has positive index and some adjacent region has smaller index. Consequently there are at least two distinct level boundaries, and the oriented smoothing yields at least two components.

Hence, whenever intersections are present, the orientation-preserving reconnection cannot produce a single curve.

The only exception is the trivial case when there are no intersections at all and the original picture already consists of one oriented simple closed curve.

This completes the proof.

∎

Verification of Key Steps

The injection in part (1) requires care. A careless argument might say that every resulting curve bounds some region and stop there. That does not exclude two curves corresponding to the same region. The crucial point is that a resulting curve carries a specific adjacent region continuously along one side. If two different curves had the same adjacent region, that region would have two distinct boundary components. The annular region between those components would itself be a complementary region, contradicting the identification of both curves with the same region.

For part (2), the Euler-circuit construction must be translated into reconnections. At a degree-$4$ vertex, the Euler circuit visits the vertex twice. Each visit pairs one entering half-edge with one leaving half-edge. These two pairings exhaust the four half-edges and define exactly one of the admissible reconnections. After performing all such pairings, the Euler circuit becomes the unique component of the smoothed graph.

For part (3), the delicate issue is the region-index function. The definition starts from the outer region with index $0$. Crossing an oriented edge from right to left increases the index by $1$. Around a crossing, consistency forces the pattern

$$n,\ n+1,\ n+2,\ n+1.$$

The oriented smoothing joins the branches that keep the same index-$n+1$ regions adjacent. This local check is the reason every smoothed component becomes a boundary between consecutive index levels. Without verifying this local configuration, the conclusion about the number of components would lack justification.

Alternative Approaches

Part (1) can also be proved using Euler's formula. Let $k$ be the number of curves after smoothing. The smoothed graph has the same edges as the original graph and all vertices have degree $2$. Applying Euler's formula to the original $4$-regular graph and comparing it with the Euler characteristic of the smoothed graph yields the inequality $k\le F$. The region-assignment argument is more geometric and directly explains why each component corresponds to a distinct original region.

For part (3), one may use the language of Seifert circles from knot theory. The oriented smoothing of every crossing produces the Seifert circles of the diagram. A classical fact states that a diagram with at least one crossing has at least two Seifert circles. The region-index proof is preferable here because it is self-contained and uses only planar topology and the orientation rule given in the problem.