Kvant Math Problem 457

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m44s
Source on kvant.digital

Problem

A non-self-intersecting closed polygonal line is given in the plane, with no three of its vertices lying on a single straight line. Call a pair of nonadjacent sides special if the extension of one of them intersects the other (Fig. 1). Prove that the number of special pairs is even.

Figure 1

S. V. Fomin

All-Union Mathematical Olympiad for School Students (XI, 1977, Grade 8)

Exploration

Let the vertices of the simple closed polygonal line be $A_1,A_2,\dots,A_n$ in cyclic order, and let $e_i=A_iA_{i+1}$, with indices taken modulo $n$.

A special pair consists of two nonadjacent sides $e_i,e_j$ such that the line containing one side meets the other side. Since the polygon is simple, the sides themselves do not intersect. Hence if the line containing $e_i$ meets the segment $e_j$, the intersection point lies on $e_j$ but outside $e_i$.

The statement concerns parity, so a natural idea is to count special pairs modulo $2$. For a fixed side $e_i$, let $s_i$ be the number of sides nonadjacent to $e_i$ whose segments are intersected by the line $\ell_i$ containing $e_i$. Then the total number of special pairs is

$$S=\sum_{i=1}^{n}s_i,$$

because for a special pair exactly one of the two lines can meet the other segment. Indeed, if the line of $e_i$ met $e_j$ and the line of $e_j$ met $e_i$, then the two segments would intersect, contradicting simplicity.

The problem becomes one of proving that $\sum s_i$ is even.

For a fixed line $\ell_i$, traverse the polygon. Each time the polygon crosses $\ell_i$, one vertex moves from one side of $\ell_i$ to the other. Since the polygon is closed, the total number of crossings of $\ell_i$ by the polygon must be even. The side $e_i$ itself lies on $\ell_i$. The two sides adjacent to $e_i$ meet $\ell_i$ at its endpoints. Every other crossing corresponds exactly to a side whose segment intersects $\ell_i$.

This suggests that the number of intersections of $\ell_i$ with nonadjacent sides has even parity. The delicate point is determining its parity precisely, because the adjacent sides contribute two endpoint contacts. After checking small examples, one finds that the number of nonadjacent sides intersected by $\ell_i$ is odd. Then each $s_i$ is odd, and

$$S\equiv n \pmod 2.$$

This cannot be the desired conclusion, since $n$ need not be even. Hence this count is not the right quantity.

The mistake is that $s_i$ counts all intersections of $\ell_i$ with nonadjacent sides, whereas a special pair requires, in addition, that the intersection point lie on the segment $e_j$. We need a more local interpretation.

Consider the vertices relative to $\ell_i$. Because no three vertices are collinear, every vertex except the endpoints of $e_i$ lies strictly on one side of $\ell_i$. Along the cyclic sequence of vertices, each change of sign corresponds to a side crossing $\ell_i$. The number of such changes is even. The sides intersected by $\ell_i$ can therefore be paired naturally. Between two consecutive crossings along the polygon, the polygon stays on one side of $\ell_i$.

The crucial observation is that a side $e_j$ is special with respect to $e_i$ exactly when the endpoints of $e_j$ lie on opposite sides of $\ell_i$. Thus special pairs correspond to crossings of the line of one side by another side. Counting all such incidences, each line $\ell_i$ is crossed by an even number of sides. Summing over all $i$ immediately yields an even total.

The only point requiring careful proof is the equivalence between “$\ell_i$ intersects $e_j$” and “the pair $(e_i,e_j)$ is special”.

Problem Understanding

We are given a simple closed polygonal line in the plane. No three vertices are collinear. Two nonadjacent sides form a special pair if the extension of one side intersects the other side.

The problem asks us to prove that the total number of special pairs is even.

This is a Type B problem. The claim is already stated and must be proved.

The core difficulty is finding a counting interpretation that converts the geometric condition defining a special pair into a parity statement. The natural object to count is the set of incidences in which the supporting line of one side intersects another side.

Proof Architecture

For each side $e_i$, let $\ell_i$ be its supporting line.

Lemma 1. For every nonadjacent side $e_j$, the pair ${e_i,e_j}$ is special if and only if $\ell_i$ intersects the segment $e_j$.

The reason is that the definition of a special pair is exactly the existence of such an intersection for one of the two supporting lines.

Lemma 2. For every side $e_i$, the number of nonadjacent sides intersected by $\ell_i$ is even.

The reason is that, as one traverses the closed polygon, crossings of a fixed line occur in pairs.

Lemma 3. The total number of special pairs equals the sum, over all sides $e_i$, of the numbers of nonadjacent sides intersected by $\ell_i$.

The reason is that each special pair contributes exactly one incidence.

The hardest point is proving that each special pair contributes exactly one incidence rather than two.

Solution

Let the sides of the polygon be

$$e_1,e_2,\dots,e_n,$$

and let $\ell_i$ denote the line containing $e_i$.

For each $i$, let $c_i$ be the number of sides of the polygon that are nonadjacent to $e_i$ and whose segments intersect the line $\ell_i$.

We first prove that every $c_i$ is even.

Fix $i$. Since no three vertices are collinear, every vertex not belonging to $e_i$ lies strictly on one side of $\ell_i$ or the other. Traverse the vertices of the polygon in cyclic order. Whenever two consecutive vertices lie on opposite sides of $\ell_i$, the corresponding side intersects $\ell_i$. Conversely, every side not contained in $\ell_i$ that intersects $\ell_i$ has endpoints on opposite sides of $\ell_i$.

Because the polygon is closed, after one complete traversal we return to the initial side of $\ell_i$. Hence the number of changes from one side of $\ell_i$ to the other is even. Therefore the number of sides intersecting $\ell_i$ is even.

Among these intersecting sides, the two sides adjacent to $e_i$ meet $\ell_i$ at the endpoints of $e_i$. Removing those two sides decreases the count by $2$, which preserves parity. Consequently

$$c_i\equiv 0 \pmod 2.$$

Now consider all incidences of the form

“the line $\ell_i$ intersects a nonadjacent side $e_j$”.

The total number of such incidences is

$$C=\sum_{i=1}^{n} c_i.$$

Since every $c_i$ is even, $C$ is even.

It remains to relate $C$ to the number of special pairs.

Take a pair of nonadjacent sides $e_i$ and $e_j$.

If $\ell_i$ intersects $e_j$, then by definition the pair is special. Likewise, if $\ell_j$ intersects $e_i$, the pair is special.

Both situations cannot occur simultaneously. Indeed, if $\ell_i$ intersects $e_j$ and $\ell_j$ intersects $e_i$, then the intersection point of the two lines belongs to both segments $e_i$ and $e_j$. The segments would intersect, contradicting the assumption that the polygonal line is non-self-intersecting and that the sides are nonadjacent.

Hence a special pair contributes exactly one incidence to the count $C$.

Conversely, every incidence counted in $C$ comes from a special pair.

Therefore the number of special pairs is exactly $C$.

Since $C$ is even, the number of special pairs is even.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the assertion that the number of sides intersecting a fixed line $\ell_i$ is even. Label each vertex not on $\ell_i$ by $+$ or $-$ according to the side of the line on which it lies. A side intersects $\ell_i$ precisely when consecutive labels differ. Along a cyclic sequence, every transition $+\to-$ must eventually be matched by a transition $-\to+$ before the cycle closes. Hence the number of transitions is even. This argument avoids any appeal to geometric intuition.

The second delicate step is the claim that a special pair contributes exactly one incidence. Suppose both incidences occurred. Then $\ell_i$ meets $e_j$ at a point $P$ of the segment $e_j$, and $\ell_j$ meets $e_i$ at the same intersection point of the two lines. Thus $P$ belongs to both segments. Nonadjacent sides of a simple polygon cannot have a common point. The contradiction shows that double counting cannot occur.

A careless argument might overlook the possibility that the two supporting lines coincide. That cannot happen here, because if two nonadjacent sides lay on the same line, then that line would contain at least three vertices of the polygon, contrary to the hypothesis that no three vertices are collinear.

Alternative Approaches

One may orient every side and consider the signs of all vertices relative to its supporting line. For a fixed side $e_i$, each nonadjacent side crossed by $\ell_i$ corresponds to a sign change in the cyclic sequence of vertex signs. Since sign changes occur an even number of times, the contribution of $e_i$ is even. Summing over all sides gives the parity result directly.

Another approach uses the Jordan curve theorem. A line intersects a simple closed polygonal curve in an even number of points, counting transversal intersections. Applying this to the supporting line of each side and removing the two intersections occurring at the adjacent vertices yields an even number of crossings with nonadjacent sides. The remainder of the proof proceeds through the same incidence count. The combinatorial sign change argument is preferable because it avoids invoking a topological theorem and makes the parity mechanism completely explicit.