Kvant Math Problem 927

The problem asks whether a sequence of allowed replacements can form a nontrivial cycle.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m09s
Source on kvant.digital

Problem

A finite set of points is given in the plane, with no three of them lying on the same line. Several segments have been drawn with endpoints at the given points. These segments may be modified: if two of them, $AC$ and $BD$, intersect, they may be erased and replaced by:

  1. the segments $AB$ and $CD$,
  2. the segments $AB$ and $BC$.

(If a “new” segment has already been drawn, it need not be drawn a second time.)

Is it possible, after several such replacements (using only rule a) or only rule b), but not both), to return to the original set of segments?

V. E. Kolosov

Exploration

The problem asks whether a sequence of allowed replacements can form a nontrivial cycle. Since only one rule is used throughout, the two rules should be analyzed separately.

For rule (a), the replacement

$$AC,\ BD \longrightarrow AB,\ CD$$

occurs when the segments $AC$ and $BD$ cross. Let the four endpoints be ordered around the convex quadrilateral as $A,B,C,D$. Then $AC$ and $BD$ are the diagonals, while $AB$ and $CD$ are sides. The operation removes two crossing segments and replaces them by two noncrossing segments. This suggests counting intersections. Each application certainly destroys the intersection between $AC$ and $BD$. The question is whether it can create new intersections elsewhere. If the total number of intersections of drawn segments never increases, one still needs strict decrease. The crucial point is to find a quantity that decreases by at least one at every move.

A more geometric quantity is the total length of all drawn segments. In a convex quadrilateral,

$$AC+BD>AB+CD,$$

because in triangles $ABC$ and $BCD$,

$$AC<AB+BC,\qquad BD<BC+CD,$$

and adding gives

$$AC+BD<AB+CD+2BC.$$

This is not enough. A better comparison comes from the fact that the diagonals of a convex quadrilateral are longer than either pair of opposite sides. Testing a square gives

$$2\sqrt2>2.$$

This suggests total length decreases. The standard proof uses the intersection point $O$:

$$AC+BD=(AO+OC)+(BO+OD)$$

and

$$AB<AO+OB,\qquad CD<CO+OD.$$

Adding yields

$$AB+CD<AC+BD.$$

Hence every move of type (a) strictly decreases total length. Then a cycle is impossible.

For rule (b),

$$AC,\ BD \longrightarrow AB,\ BC.$$

Now the number of segments may change because one or both new segments may already be present. Looking for a monotone quantity, the total number of drawn segments is not monotone. Vertex degrees seem promising.

Let $d(X)$ denote the degree of vertex $X$. Before the move, the four involved edges contribute

$$A:1,\quad B:1,\quad C:1,\quad D:1.$$

After the move,

$$A:1,\quad B:2,\quad C:2,\quad D:0.$$

Thus the sum of degrees is unchanged, but

$$d(B)+d(C)$$

increases while $d(D)$ decreases.

A standard invariant for edge-rewriting processes is

$$\Phi=\sum_v d(v)^2.$$

Computing the change:

$$(d_B+1)^2-d_B^2=2d_B+1,$$

$$(d_C+1)^2-d_C^2=2d_C+1,$$

$$(d_D-1)^2-d_D^2=-2d_D+1.$$

Vertex $A$ is unchanged. Hence

$$\Delta\Phi =2(d_B+d_C-d_D)+3.$$

At the moment of the move, edges $AB$ and $BC$ are absent, otherwise they would not need to be drawn. Therefore $d_B\ge1$ because of $BD$, $d_C\ge1$ because of $AC$, and $d_D\ge1$ because of $BD$. The minimum of the expression occurs at

$$d_B=d_C=d_D=1,$$

giving

$$\Delta\Phi=5>0.$$

So $\Phi$ strictly increases at every move. A cycle is impossible.

The delicate point is handling the convention that an already existing “new” segment is not drawn again. Degrees must then be interpreted in the graph of distinct segments. The change in $\Phi$ should be computed using the actual graph. If $AB$ already existed, then that edge would contribute neither before nor after; similarly for $BC$. In that case the degree increase at $B$ or $C$ is smaller, not larger. A cleaner approach is to use the number

$$\Psi=\sum_v d(v).$$

No, that is not strictly monotone. We need a quantity robust under preexisting edges.

Let $E$ be the set of drawn segments. Since duplicate segments are ignored, the operation replaces $AC$ and $BD$ by adding $AB$ and $BC$ if absent. Consider

$$F=\sum_v d(v)^2.$$

Let $\alpha,\beta\in{0,1}$ indicate whether $AB,BC$ are absent before the move. Then degree changes are

$$\Delta d_A=\alpha-1,\quad \Delta d_B=\alpha+\beta-1,$$

$$\Delta d_C=\beta-1,\quad \Delta d_D=-1.$$

Since $AC$ and $BD$ are present, $d_A,d_C,d_B,d_D\ge1$. A direct computation shows

$$\Delta F =2d_A(\alpha-1)+(\alpha-1)^2 +2d_B(\alpha+\beta-1)+(\alpha+\beta-1)^2$$

$$+2d_C(\beta-1)+(\beta-1)^2 +2d_D(-1)+1.$$

This is messy.

A better idea: orient the plane. Choose a direction not perpendicular to any segment joining two given points. Let $x(P)$ be the coordinate of point $P$ on that direction. Number the points by increasing $x$.

For a segment $UV$, define its span as $|x(U)-x(V)|$. Under rule (b), with points ordered $A,B,C,D$ around the convex quadrilateral, one has

$$x(A)<x(B)<x(C)<x(D)$$

after relabeling according to the chosen direction. Then

$$|AC|_x+|BD|_x=(x_C-x_A)+(x_D-x_B),$$

while

$$|AB|_x+|BC|_x=x_C-x_A.$$

The total span decreases by $x_D-x_B>0$. This works even if $AB$ or $BC$ already existed, because then the total span decreases even more: we remove $AC$ and $BD$ but add at most those two segments. This gives a strict monotone quantity.

The same span argument also works for rule (a):

$$(x_C-x_A)+(x_D-x_B)$$

is replaced by

$$(x_B-x_A)+(x_D-x_C),$$

and the decrease equals

$$2(x_C-x_B)>0.$$

Thus one common invariant suffices.

Problem Understanding

We are given a finite graph whose vertices are fixed points in the plane and whose edges are drawn segments. Whenever two drawn segments $AC$ and $BD$ intersect, we may replace them either by $AB$ and $CD$ (rule (a)) or by $AB$ and $BC$ (rule (b)). During the whole process only one of the two rules is allowed.

The question is whether, after a finite nonempty sequence of such replacements, one can obtain exactly the original set of drawn segments again.

This is a Type A problem. We must determine, separately for each rule, whether such a return is possible.

The core difficulty is to find a quantity attached to the set of segments that changes strictly in one direction under every allowed replacement, even when one or both newly created segments already exist.

The answer is that no return is possible for either rule. A suitable weighted sum of the spans of all drawn segments strictly decreases at every move.

Proof Architecture

Choose a direction in the plane that is not perpendicular to any line joining two given points, and let $x(P)$ denote the coordinate of a point $P$ on this direction.

Define the span of a segment $UV$ by $s(UV)=|x(U)-x(V)|$, and define $S$ as the sum of the spans of all drawn segments.

Lemma 1. If two segments $AC$ and $BD$ intersect, then after possibly renaming the endpoints one has

$$x(A)<x(B)<x(C)<x(D).$$

This follows because the endpoints of two crossing segments alternate in the order determined by any projection direction avoiding equal coordinates.

Lemma 2. Under rule (a), the quantity $S$ decreases by

$$2\bigl(x(C)-x(B)\bigr)>0.$$

This is obtained by comparing the spans of the removed and added segments.

Lemma 3. Under rule (b), the quantity $S$ decreases by at least

$$x(D)-x(B)>0.$$

This remains true even if one or both added segments already existed.

The hardest point is Lemma 1, because the span computations depend on the alternating order of the endpoints of two crossing segments.

Solution

Choose a direction in the plane that is not perpendicular to any segment joining two of the given points. Since the set of points is finite, such a direction exists. Let $x(P)$ be the coordinate of a point $P$ on the axis determined by this direction. Then distinct points have distinct $x$-coordinates.

For every drawn segment $UV$, define

$$s(UV)=|x(U)-x(V)|.$$

Let

$$S=\sum s(UV),$$

where the sum is taken over all drawn segments. Since the set of segments is finite, $S$ is finite.

Consider an allowed replacement. The segments $AC$ and $BD$ intersect. Because the four endpoints are vertices of a convex quadrilateral and the two intersecting segments are its diagonals, the endpoints alternate along every line projection that assigns distinct coordinates to them. After renaming the points if necessary,

$$x(A)<x(B)<x(C)<x(D).$$

First suppose rule (a) is used. The segments $AC$ and $BD$ are removed, and the segments $AB$ and $CD$ are added.

The total span removed equals

$$(x(C)-x(A))+(x(D)-x(B)).$$

The total span added is at most

$$(x(B)-x(A))+(x(D)-x(C)),$$

because if one of the segments $AB$ or $CD$ already exists, the actual increase of $S$ is smaller.

Hence

$$\Delta S \le (x(B)-x(A))+(x(D)-x(C))$$

$$-(x(C)-x(A))-(x(D)-x(B)) = -2\bigl(x(C)-x(B)\bigr).$$

Since $x(C)>x(B)$,

$$\Delta S<0.$$

Thus every application of rule (a) strictly decreases $S$.

Now suppose rule (b) is used. The segments $AC$ and $BD$ are removed, and the segments $AB$ and $BC$ are added.

The total span removed equals

$$(x(C)-x(A))+(x(D)-x(B)).$$

The total span added is at most

$$(x(B)-x(A))+(x(C)-x(B)) = x(C)-x(A).$$

Therefore

$$\Delta S \le (x(C)-x(A)) - \bigl((x(C)-x(A))+(x(D)-x(B))\bigr) = -(x(D)-x(B)).$$

Since $x(D)>x(B)$,

$$\Delta S<0.$$

Thus every application of rule (b) also strictly decreases $S$.

In either case, $S$ decreases at every replacement. Consequently a nonempty sequence of replacements cannot return to the original set of segments, because that would require $S$ to recover its original value.

Hence returning to the original configuration is impossible when only rule (a) is used, and it is also impossible when only rule (b) is used.

$$\boxed{\text{For neither rule is it possible to return to the original set of segments.}}$$

Verification of Key Steps

The first delicate step is the ordering

$$x(A)<x(B)<x(C)<x(D).$$

If two segments $AC$ and $BD$ cross, their endpoints alternate on the boundary of the convex quadrilateral formed by the four points. Projecting onto a direction for which no two points have the same coordinate preserves this alternation in the sense that one diagonal joins the first and third projected points, while the other joins the second and fourth. A careless argument might assume the ordering without justifying why crossing forces alternation.

The second delicate step is the treatment of already existing segments. In rule (a), if $AB$ already exists, the increase of $S$ is smaller than $s(AB)+s(CD)$; it is not equal to that quantity. Using an inequality rather than an equality is essential. The same issue occurs in rule (b). The proof only needs an upper bound for the increase and therefore remains valid.

The third delicate step is the computation for rule (b):

$$s(AB)+s(BC) = (x(B)-x(A))+(x(C)-x(B)) = x(C)-x(A).$$

Subtracting the removed span yields

$$-(x(D)-x(B)),$$

which is strictly negative because the four projected coordinates are distinct. Missing this cancellation obscures the monotonicity.

Alternative Approaches

For rule (a), one may use the total Euclidean length of all drawn segments. Let $O$ be the intersection point of $AC$ and $BD$. Then

$$AB<AO+OB,\qquad CD<CO+OD.$$

Adding these inequalities gives

$$AB+CD<AC+BD.$$

Hence the total length strictly decreases. This proves impossibility of a cycle for rule (a).

That argument does not adapt naturally to rule (b). The projection method treats both rules uniformly and automatically handles the possibility that a newly created segment was already present. For this reason the span invariant provides the most economical complete solution.